Smoothed analysis of the successive shortest path algorithm

Tobias Brunsch; Kamiel Cornelissen; Bodo Manthey; Heiko Röglin

Smoothed analysis of the successive shortest path algorithm

Tobias Brunsch
, Kamiel Cornelissen
, Bodo Manthey
, Heiko Röglin

Discrete Mathematics and Mathematical Programming

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

7 Citations (Scopus)

44 Downloads (Pure)

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	English
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	Proceedings ACM-SIAM Symposium on Discrete Algorithms
Publisher	SIAM
Number	24
Volume	2013
ISSN (Print)	1557-9468

Conference

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

Keywords

Min-cost flow
Smoothed Analysis
Minimum-cost flow
2023 OA procedure

Access to Document

ArticleFinal published version, 420 KBLicence: Taverne

https://dl.acm.org/doi/10.5555/2627817.2627902

7 Citations
1 Paper
1 Article

Smoothed Analysis of the Successive Shortest Path Algorithm
Brunsch, T., Cornelissen, K., Manthey, B., Röglin, H. & Rösner, C., 2015, In: SIAM journal on computing. 44, 6, p. 1798-1819 22 p.
Research output: Contribution to journal › Article › Academic › peer-review

Open Access
File
8 Link opens in a new tab Citations (Scopus)

58 Downloads (Pure)
Smoothed analysis of the successive shortest path algorithm
Brunsch, T., Cornelissen, K., Hurink, J. L., Manthey, B. & Röglin, H., 2013, p. 27-30. 4 p.
Research output: Contribution to conference › Paper › peer-review

Open Access
File

Cite this

@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 = "Min-cost flow, Smoothed Analysis, Minimum-cost flow, 2023 OA procedure",

author = "Tobias Brunsch and Kamiel Cornelissen and Bodo Manthey and Heiko R{\"o}glin",

year = "2013",

language = "English",

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

series = "Proceedings ACM-SIAM Symposium on Discrete Algorithms",

publisher = "SIAM",

number = "24",

pages = "1180--1189",

editor = "S. Khanna",

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

address = "United States",

note = "24th ACM-SIAM Symposium on Discrete Algorithms 2013, SODA 2013 ; Conference date: 06-01-2013 Through 08-01-2013",

url = "https://archive.siam.org/meetings/da13/",

}

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. Proceedings ACM-SIAM Symposium on Discrete Algorithms, no. 24, vol. 2013, SIAM, New Orleans, LA, USA, pp. 1180-1189, 24th ACM-SIAM Symposium on Discrete Algorithms 2013, New Orleans, Louisiana, United States, 6/01/13. <https://dl.acm.org/doi/10.5555/2627817.2627902>

Smoothed analysis of the successive shortest path algorithm. / Brunsch, Tobias; Cornelissen, Kamiel; Manthey, Bodo et al.
Proceedings of the 24th ACM-SIAM Symposium on Discrete Algorithms. ed. / S. Khanna. New Orleans, LA, USA: SIAM, 2013. p. 1180-1189 (Proceedings ACM-SIAM Symposium on Discrete Algorithms; Vol. 2013, No. 24).

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, Tobias

AU - Cornelissen, Kamiel

AU - Manthey, Bodo

AU - Röglin, Heiko

N1 - Conference code: 24

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 - Min-cost flow

KW - Smoothed Analysis

KW - Minimum-cost flow

KW - 2023 OA procedure

M3 - Conference contribution

SN - 978-1-611972-52-8

T3 - Proceedings ACM-SIAM Symposium on Discrete Algorithms

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

T2 - 24th ACM-SIAM Symposium on Discrete Algorithms 2013

Y2 - 6 January 2013 through 8 January 2013

ER -

Smoothed analysis of the successive shortest path algorithm

Abstract

Publication series

Conference

Keywords

Access to Document

Fingerprint

Research output

Smoothed Analysis of the Successive Shortest Path Algorithm

Smoothed analysis of the successive shortest path algorithm

Cite this