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

97 Downloads (Pure)


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(mn) when phi = Omega(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 13th Cologne-Twente Workshop on Graphs and Combinatorial Optimization
EditorsA.F. Alkaya, E. Duman
Place of PublicationIstanbul
PublisherOzyegin Universitesi and Marmara Universitesi
Number of pages4
ISBN (Print)not assigned
Publication statusPublished - 26 May 2015
Event13th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2015 - Marmara University , Istanbul, Turkey
Duration: 26 May 201528 May 2015
Conference number: 13

Publication series

PublisherÖzyegin Üniversitesi and Marmara Üniversitesi


Workshop13th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2015
Abbreviated titleCTW
Internet address


  • EWI-25943
  • IR-96322
  • METIS-312556

Cite this