Tight bounds on the number of minimum-mean cycle cancellations and related results

DOI10.1007/BF01240734zbMath0795.68098OpenAlexW3138503030MaRDI QIDQ1317475

Andrew V. Goldberg, Tomasz Radzik

Publication date: 11 September 1994

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01240734

zbMATH Keywords

combinatorial optimizationnetwork flow problemminimum cost flowdual algorithmstrongly polynomial algorithmsminimum cost circulationcycle cancelling algorithmsmaximum- mean cut canceling algorithmminimum-mean cycle-cancelling algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Deterministic network models in operations research (90B10)

Related Items

Smoothed Analysis of the Successive Shortest Path Algorithm ⋮ Smoothed Analysis of the Minimum-Mean Cycle Canceling Algorithm and the Network Simplex Algorithm ⋮ A strongly polynomial contraction-expansion algorithm for network flow problems ⋮ Smoothed Analysis of the Minimum-Mean Cycle Canceling Algorithm and the Network Simplex Algorithm ⋮ About the minimum mean cycle-canceling algorithm ⋮ A new approach for computing a most positive cut using the minimum flow algorithms ⋮ Decomposition theorems for linear programs ⋮ Engineering Negative Cycle Canceling for Wind Farm Cabling ⋮ The minimum mean cycle-canceling algorithm for linear programs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A strongly polynomial minimum cost circulation algorithm
• Finding minimum-cost flows by double scaling
• A characterization of the minimum cycle mean in a digraph
• A new saling algorithm for the maximum mean cut problem
• Monotone networks
• Finding Minimum-Cost Circulations by Successive Approximation
• Finding minimum-cost circulations by canceling negative cycles
• An Out-of-Kilter Method for Minimal-Cost Flow Problems
• The minimum cost flow problem: A unifying approach to dual algorithms and a new tree-search algorithm
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
• Diagonal similarity and equivalence for matrices over groups with 0
• A bad network problem for the simplex method and other minimum cost flow algorithms
• More pathological examples for network flow problems
• A Primal Method for Minimal Cost Flows with Applications to the Assignment and Transportation Problems