Smoothed analysis of the successive shortest path algorithm

T. Brunsch; Kamiel Cornelissen; Bodo Manthey; H. Röglin

Smoothed analysis of the successive shortest path algorithm

T. Brunsch, Kamiel Cornelissen, Bodo Manthey, H. Röglin

Discrete Mathematics and Mathematical Programming

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

6 Citations (Scopus)

Abstract

The minimum-cost flow problem is a classic problem in combinatorial optimization with various applications. Several pseudo-polynomial, polynomial, and strongly polynomial algorithms have been developed in the past decades, and it seems that both the problem and the algorithms are well understood. However, some of the algorithms' running times observed in empirical studies contrast the running times obtained by worst-case analysis not only in the order of magnitude but also in the ranking when compared to each other. For example, the Successive Shortest Path (SSP) algorithm, which has an exponential worst-case running time, seems to outperform the strongly polynomial Minimum-Mean Cycle Canceling algorithm. To explain this discrepancy, we study the SSP algorithm in the framework of smoothed analysis and establish a bound of O(mn phi (m + n log n)) for its smoothed running time. This shows that worst-case instances for the SSP algorithm are not robust and unlikely to be encountered in practice.

Original language	Undefined
Title of host publication	Proceedings of the 24th ACM-SIAM Symposium on Discrete Algorithms
Editors	S. Khanna
Place of Publication	New Orleans, LA, USA
Publisher	SIAM
Pages	1180-1189
Number of pages	10
ISBN (Print)	978-1-611972-52-8
Publication status	Published - 2013
Event	24th ACM-SIAM Symposium on Discrete Algorithms 2013 - Astor Crowne Plaza Hotel, New Orleans, United States Duration: 6 Jan 2013 → 8 Jan 2013 Conference number: 24 https://archive.siam.org/meetings/da13/

Publication series

Name
Publisher	SIAM
ISSN (Print)	1557-9468

Conference

Conference	24th ACM-SIAM Symposium on Discrete Algorithms 2013
Abbreviated title	SODA 2013
Country	United States
City	New Orleans
Period	6/01/13 → 8/01/13
Internet address	https://archive.siam.org/meetings/da13/

Keywords

METIS-296428
Min-cost flow
Smoothed Analysis
IR-82805
EWI-22219
Minimum-cost flow

Access to Document

Cite this

Brunsch, T., Cornelissen, K., Manthey, B., & Röglin, H. (2013). Smoothed analysis of the successive shortest path algorithm. In S. Khanna (Ed.), Proceedings of the 24th ACM-SIAM Symposium on Discrete Algorithms (pp. 1180-1189). New Orleans, LA, USA: SIAM.

@inproceedings{8011be1588124107af92b9bfa5eae603,

title = "Smoothed analysis of the successive shortest path algorithm",

abstract = "The minimum-cost flow problem is a classic problem in combinatorial optimization with various applications. Several pseudo-polynomial, polynomial, and strongly polynomial algorithms have been developed in the past decades, and it seems that both the problem and the algorithms are well understood. However, some of the algorithms' running times observed in empirical studies contrast the running times obtained by worst-case analysis not only in the order of magnitude but also in the ranking when compared to each other. For example, the Successive Shortest Path (SSP) algorithm, which has an exponential worst-case running time, seems to outperform the strongly polynomial Minimum-Mean Cycle Canceling algorithm. To explain this discrepancy, we study the SSP algorithm in the framework of smoothed analysis and establish a bound of O(mn phi (m + n log n)) for its smoothed running time. This shows that worst-case instances for the SSP algorithm are not robust and unlikely to be encountered in practice.",

keywords = "METIS-296428, Min-cost flow, Smoothed Analysis, IR-82805, EWI-22219, Minimum-cost flow",

author = "T. Brunsch and Kamiel Cornelissen and Bodo Manthey and H. R{\"o}glin",

year = "2013",

language = "Undefined",

isbn = "978-1-611972-52-8",

publisher = "SIAM",

pages = "1180--1189",

editor = "S. Khanna",

booktitle = "Proceedings of the 24th ACM-SIAM Symposium on Discrete Algorithms",

}

Smoothed analysis of the successive shortest path algorithm. / Brunsch, T.; Cornelissen, Kamiel; Manthey, Bodo; Röglin, H.

Proceedings of the 24th ACM-SIAM Symposium on Discrete Algorithms. ed. / S. Khanna. New Orleans, LA, USA : SIAM, 2013. p. 1180-1189.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Smoothed analysis of the successive shortest path algorithm

AU - Brunsch, T.

AU - Cornelissen, Kamiel

AU - Manthey, Bodo

AU - Röglin, H.

PY - 2013

Y1 - 2013

N2 - The minimum-cost flow problem is a classic problem in combinatorial optimization with various applications. Several pseudo-polynomial, polynomial, and strongly polynomial algorithms have been developed in the past decades, and it seems that both the problem and the algorithms are well understood. However, some of the algorithms' running times observed in empirical studies contrast the running times obtained by worst-case analysis not only in the order of magnitude but also in the ranking when compared to each other. For example, the Successive Shortest Path (SSP) algorithm, which has an exponential worst-case running time, seems to outperform the strongly polynomial Minimum-Mean Cycle Canceling algorithm. To explain this discrepancy, we study the SSP algorithm in the framework of smoothed analysis and establish a bound of O(mn phi (m + n log n)) for its smoothed running time. This shows that worst-case instances for the SSP algorithm are not robust and unlikely to be encountered in practice.

AB - The minimum-cost flow problem is a classic problem in combinatorial optimization with various applications. Several pseudo-polynomial, polynomial, and strongly polynomial algorithms have been developed in the past decades, and it seems that both the problem and the algorithms are well understood. However, some of the algorithms' running times observed in empirical studies contrast the running times obtained by worst-case analysis not only in the order of magnitude but also in the ranking when compared to each other. For example, the Successive Shortest Path (SSP) algorithm, which has an exponential worst-case running time, seems to outperform the strongly polynomial Minimum-Mean Cycle Canceling algorithm. To explain this discrepancy, we study the SSP algorithm in the framework of smoothed analysis and establish a bound of O(mn phi (m + n log n)) for its smoothed running time. This shows that worst-case instances for the SSP algorithm are not robust and unlikely to be encountered in practice.

KW - METIS-296428

KW - Min-cost flow

KW - Smoothed Analysis

KW - IR-82805

KW - EWI-22219

KW - Minimum-cost flow

M3 - Conference contribution

SN - 978-1-611972-52-8

SP - 1180

EP - 1189

BT - Proceedings of the 24th ACM-SIAM Symposium on Discrete Algorithms

A2 - Khanna, S.

PB - SIAM

CY - New Orleans, LA, USA

ER -