TY - JOUR

T1 - Smoothed analysis of the minimum-mean cycle canceling algorithm and the network simplex algorithm

AU - Cornelissen, Kamiel

AU - Manthey, Bodo

PY - 2020

Y1 - 2020

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 among the best algorithms in practice and performs very well 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 to NS and MMCC. We show an upper bound of O(mn2 log(n) log(φ)) for the number of iterations of the MMCC algorithm. Here, n is the number of nodes, m is the number of edges, and φ is a parameter limiting the degree to which the edge costs are perturbed. We also show a lower bound of Ω(m log(φ)) for the number of iterations of the MMCC algorithm, which can be strengthened to Ω(mn) when φ = Θ(n2 ). For the number of iterations of the NS algorithm we show a smoothed lower bound of Ω(m · min{n, φ} · φ).

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 among the best algorithms in practice and performs very well 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 to NS and MMCC. We show an upper bound of O(mn2 log(n) log(φ)) for the number of iterations of the MMCC algorithm. Here, n is the number of nodes, m is the number of edges, and φ is a parameter limiting the degree to which the edge costs are perturbed. We also show a lower bound of Ω(m log(φ)) for the number of iterations of the MMCC algorithm, which can be strengthened to Ω(mn) when φ = Θ(n2 ). For the number of iterations of the NS algorithm we show a smoothed lower bound of Ω(m · min{n, φ} · φ).

UR - http://www.scopus.com/inward/record.url?scp=85088257852&partnerID=8YFLogxK

U2 - 10.7155/jgaa.00539

DO - 10.7155/jgaa.00539

M3 - Article

AN - SCOPUS:85088257852

SN - 1526-1719

VL - 24

SP - 397

EP - 421

JO - Journal of graph algorithms and applications

JF - Journal of graph algorithms and applications

IS - 3

ER -