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

DOI10.1007/978-3-319-21398-9_55zbMath1468.90137arXiv1504.08251OpenAlexW2143902679MaRDI QIDQ3196427

Kamiel Cornelissen, Bodo Manthey

Publication date: 29 October 2015

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1504.08251

zbMATH Keywords

minimum-cost flow problem, smoothed analysis

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms (68W40)

Related Items (1)

Smoothed Analysis of Local Search Algorithms

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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
• 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

This page was built for publication: Smoothed Analysis of the Minimum-Mean Cycle Canceling Algorithm and the Network Simplex Algorithm