Smoothed Analysis of the Minimum-Mean Cycle Canceling Algorithm and the Network Simplex Algorithm

Kamiel Cornelissen, Bodo Manthey

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

Abstract

The minimum-cost flow (MCF) problem is a fundamental optimization problem with many applications and seems to be well understood. Over the last half century many algorithms have been developed to solve the MCF problem and these algorithms have varying worst-case bounds on their running time. However, these worst-case bounds are not always a good indication of the algorithms' performance in practice. The Network Simplex (NS) algorithm needs an exponential number of iterations for some instances, but it is considered the best algorithm in practice and performs best in experimental studies. On the other hand, the Minimum-Mean Cycle Canceling (MMCC) algorithm is strongly polynomial, but performs badly in experimental studies. To explain these differences in performance in practice we apply the framework of smoothed analysis. For the number of iterations of the MMCC algorithm we show an upper bound of O(m n^2 log(n) log(phi)). Here n is the number of nodes, m is the number of edges, and phi is a parameter limiting the degree to which the edge costs are perturbed. We also show a lower bound of Omega(m log(phi)) for the number of iterations of the MMCC algorithm, which can be strengthened to Omega(m n) when phi=Theta(n^2). For the number of iterations of the NS algorithm we show a smoothed lower bound of Omega(m min\{n,phi\} phi).
Original languageUndefined
Title of host publicationProceedings of the 21st Computing and Combinatorics Conference (COCOON 2015)
EditorsDachuan Xu, Donglei Du, Dingzhu Du
Place of PublicationBerlin
PublisherSpringer
Pages701-712
Number of pages12
ISBN (Print)978-3-319-21397-2
DOIs
Publication statusPublished - 4 Aug 2015
Event21st International Conference on Computing and Combinatorics, COCOON 2015 - Beijing, China
Duration: 4 Aug 20156 Aug 2015
Conference number: 21

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Verlag
Volume9198
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference21st International Conference on Computing and Combinatorics, COCOON 2015
Abbreviated titleCOCOON
CountryChina
CityBeijing
Period4/08/156/08/15

Keywords

  • EWI-25942
  • IR-96738
  • METIS-312555

Cite this

Cornelissen, K., & Manthey, B. (2015). Smoothed Analysis of the Minimum-Mean Cycle Canceling Algorithm and the Network Simplex Algorithm. In D. Xu, D. Du, & D. Du (Eds.), Proceedings of the 21st Computing and Combinatorics Conference (COCOON 2015) (pp. 701-712). (Lecture Notes in Computer Science; Vol. 9198). Berlin: Springer. https://doi.org/10.1007/978-3-319-21398-9_55
Cornelissen, Kamiel ; Manthey, Bodo. / Smoothed Analysis of the Minimum-Mean Cycle Canceling Algorithm and the Network Simplex Algorithm. Proceedings of the 21st Computing and Combinatorics Conference (COCOON 2015). editor / Dachuan Xu ; Donglei Du ; Dingzhu Du. Berlin : Springer, 2015. pp. 701-712 (Lecture Notes in Computer Science).
@inproceedings{c6f4973f18b840da9084cd894f4099ec,
title = "Smoothed Analysis of the Minimum-Mean Cycle Canceling Algorithm and the Network Simplex Algorithm",
abstract = "The minimum-cost flow (MCF) problem is a fundamental optimization problem with many applications and seems to be well understood. Over the last half century many algorithms have been developed to solve the MCF problem and these algorithms have varying worst-case bounds on their running time. However, these worst-case bounds are not always a good indication of the algorithms' performance in practice. The Network Simplex (NS) algorithm needs an exponential number of iterations for some instances, but it is considered the best algorithm in practice and performs best in experimental studies. On the other hand, the Minimum-Mean Cycle Canceling (MMCC) algorithm is strongly polynomial, but performs badly in experimental studies. To explain these differences in performance in practice we apply the framework of smoothed analysis. For the number of iterations of the MMCC algorithm we show an upper bound of O(m n^2 log(n) log(phi)). Here n is the number of nodes, m is the number of edges, and phi is a parameter limiting the degree to which the edge costs are perturbed. We also show a lower bound of Omega(m log(phi)) for the number of iterations of the MMCC algorithm, which can be strengthened to Omega(m n) when phi=Theta(n^2). For the number of iterations of the NS algorithm we show a smoothed lower bound of Omega(m min\{n,phi\} phi).",
keywords = "EWI-25942, IR-96738, METIS-312555",
author = "Kamiel Cornelissen and Bodo Manthey",
note = "10.1007/978-3-319-21398-9_55",
year = "2015",
month = "8",
day = "4",
doi = "10.1007/978-3-319-21398-9_55",
language = "Undefined",
isbn = "978-3-319-21397-2",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "701--712",
editor = "Dachuan Xu and Donglei Du and Dingzhu Du",
booktitle = "Proceedings of the 21st Computing and Combinatorics Conference (COCOON 2015)",

}

Cornelissen, K & Manthey, B 2015, Smoothed Analysis of the Minimum-Mean Cycle Canceling Algorithm and the Network Simplex Algorithm. in D Xu, D Du & D Du (eds), Proceedings of the 21st Computing and Combinatorics Conference (COCOON 2015). Lecture Notes in Computer Science, vol. 9198, Springer, Berlin, pp. 701-712, 21st International Conference on Computing and Combinatorics, COCOON 2015, Beijing, China, 4/08/15. https://doi.org/10.1007/978-3-319-21398-9_55

Smoothed Analysis of the Minimum-Mean Cycle Canceling Algorithm and the Network Simplex Algorithm. / Cornelissen, Kamiel; Manthey, Bodo.

Proceedings of the 21st Computing and Combinatorics Conference (COCOON 2015). ed. / Dachuan Xu; Donglei Du; Dingzhu Du. Berlin : Springer, 2015. p. 701-712 (Lecture Notes in Computer Science; Vol. 9198).

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

TY - GEN

T1 - Smoothed Analysis of the Minimum-Mean Cycle Canceling Algorithm and the Network Simplex Algorithm

AU - Cornelissen, Kamiel

AU - Manthey, Bodo

N1 - 10.1007/978-3-319-21398-9_55

PY - 2015/8/4

Y1 - 2015/8/4

N2 - The minimum-cost flow (MCF) problem is a fundamental optimization problem with many applications and seems to be well understood. Over the last half century many algorithms have been developed to solve the MCF problem and these algorithms have varying worst-case bounds on their running time. However, these worst-case bounds are not always a good indication of the algorithms' performance in practice. The Network Simplex (NS) algorithm needs an exponential number of iterations for some instances, but it is considered the best algorithm in practice and performs best in experimental studies. On the other hand, the Minimum-Mean Cycle Canceling (MMCC) algorithm is strongly polynomial, but performs badly in experimental studies. To explain these differences in performance in practice we apply the framework of smoothed analysis. For the number of iterations of the MMCC algorithm we show an upper bound of O(m n^2 log(n) log(phi)). Here n is the number of nodes, m is the number of edges, and phi is a parameter limiting the degree to which the edge costs are perturbed. We also show a lower bound of Omega(m log(phi)) for the number of iterations of the MMCC algorithm, which can be strengthened to Omega(m n) when phi=Theta(n^2). For the number of iterations of the NS algorithm we show a smoothed lower bound of Omega(m min\{n,phi\} phi).

AB - The minimum-cost flow (MCF) problem is a fundamental optimization problem with many applications and seems to be well understood. Over the last half century many algorithms have been developed to solve the MCF problem and these algorithms have varying worst-case bounds on their running time. However, these worst-case bounds are not always a good indication of the algorithms' performance in practice. The Network Simplex (NS) algorithm needs an exponential number of iterations for some instances, but it is considered the best algorithm in practice and performs best in experimental studies. On the other hand, the Minimum-Mean Cycle Canceling (MMCC) algorithm is strongly polynomial, but performs badly in experimental studies. To explain these differences in performance in practice we apply the framework of smoothed analysis. For the number of iterations of the MMCC algorithm we show an upper bound of O(m n^2 log(n) log(phi)). Here n is the number of nodes, m is the number of edges, and phi is a parameter limiting the degree to which the edge costs are perturbed. We also show a lower bound of Omega(m log(phi)) for the number of iterations of the MMCC algorithm, which can be strengthened to Omega(m n) when phi=Theta(n^2). For the number of iterations of the NS algorithm we show a smoothed lower bound of Omega(m min\{n,phi\} phi).

KW - EWI-25942

KW - IR-96738

KW - METIS-312555

U2 - 10.1007/978-3-319-21398-9_55

DO - 10.1007/978-3-319-21398-9_55

M3 - Conference contribution

SN - 978-3-319-21397-2

T3 - Lecture Notes in Computer Science

SP - 701

EP - 712

BT - Proceedings of the 21st Computing and Combinatorics Conference (COCOON 2015)

A2 - Xu, Dachuan

A2 - Du, Donglei

A2 - Du, Dingzhu

PB - Springer

CY - Berlin

ER -

Cornelissen K, Manthey B. Smoothed Analysis of the Minimum-Mean Cycle Canceling Algorithm and the Network Simplex Algorithm. In Xu D, Du D, Du D, editors, Proceedings of the 21st Computing and Combinatorics Conference (COCOON 2015). Berlin: Springer. 2015. p. 701-712. (Lecture Notes in Computer Science). https://doi.org/10.1007/978-3-319-21398-9_55