Smoothed Analysis of the Successive Shortest Path Algorithm

DOI10.1137/140989893zbMath1326.05039arXiv1501.05493OpenAlexW2480513428MaRDI QIDQ3457194

Kamiel Cornelissen, Heiko Röglin, Clemens Rösner, Tobias Brunsch, Bodo Manthey

Publication date: 11 December 2015

Published in: SIAM Journal on Computing (Search for Journal in Brave)

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

zbMATH Keywords

smoothed analysissuccessive shortest path algorithmminimum-cost flows

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Combinatorial optimization (90C27) Paths and cycles (05C38) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (4)

Smoothed Analysis of Local Search Algorithms ⋮ Smoothed Analysis of the Minimum-Mean Cycle Canceling Algorithm and the Network Simplex Algorithm ⋮ Smoothed Analysis of the Minimum-Mean Cycle Canceling Algorithm and the Network Simplex Algorithm ⋮ A Friendly Smoothed Analysis of the Simplex Method

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A strongly polynomial minimum cost circulation algorithm
• Tight bounds on the number of minimum-mean cycle cancellations and related results
• On dual minimum cost flow algorithms
• Minimum-cost flow algorithms: an experimental evaluation
• Monotone networks
• Finding Minimum-Cost Circulations by Successive Approximation
• Finding minimum-cost circulations by canceling negative cycles
• Beyond Hirsch Conjecture: Walks on Random Polytopes and Smoothed Complexity of the Simplex Method
• 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
• Finding Short Paths on Polytopes by the Shadow Vertex Algorithm
• Typical Properties of Winners and Losers [0.2ex in Discrete Optimization]
• A Primal Method for Minimal Cost Flows with Applications to the Assignment and Transportation Problems
• Random knapsack in expected polynomial time
• Combinatorial optimization. Theory and algorithms.

This page was built for publication: Smoothed Analysis of the Successive Shortest Path Algorithm