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

DOI10.7155/jgaa.00539zbMath1477.90117OpenAlexW3042420402MaRDI QIDQ5119385

Bodo Manthey, Kamiel Cornelissen

Publication date: 4 September 2020

Published in: Journal of Graph Algorithms and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.7155/jgaa.00539

zbMATH Keywords

worst case analysissmoothed analysismin-cost flow

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• About the minimum mean cycle-canceling algorithm
• A strongly polynomial minimum cost circulation algorithm
• A characterization of the minimum cycle mean in a digraph
• Tight bounds on the number of minimum-mean cycle cancellations and related results
• A polynomial time primal network simplex algorithm for minimum cost flows
• Combinatorial optimization. Theory and applications.
• Minimum-cost flow algorithms: an experimental evaluation
• Monotone networks
• Smoothed Analysis of the Successive Shortest Path Algorithm
• Finding minimum-cost circulations by canceling negative cycles
• Smoothed analysis of algorithms
• New Methods in Mathematical Programming—Optimal Flow Through Networks with Gains
• An Out-of-Kilter Method for Minimal-Cost Flow Problems
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
• A bad network problem for the simplex method and other minimum cost flow algorithms
• A Faster Strongly Polynomial Minimum Cost Flow Algorithm
• A Primal Method for Minimal Cost Flows with Applications to the Assignment and Transportation Problems
• Random knapsack in expected polynomial time