About the minimum mean cycle-canceling algorithm

DOI10.1016/j.dam.2014.07.005zbMath1331.90088OpenAlexW2153601281MaRDI QIDQ499347

Jean Bertrand Gauthier, Marco E. Lübbecke, Jacques Desrosiers

Publication date: 30 September 2015

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2014.07.005

zbMATH Keywords

network flow problemcomplexity analysisstrongly polynomial algorithmflow decompositionminimum mean cycleresidual network

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Related Items (8)

Heterogeneous Multi-resource Allocation with Subset Demand Requests ⋮ Smoothed Analysis of the Minimum-Mean Cycle Canceling Algorithm and the Network Simplex Algorithm ⋮ A strongly polynomial contraction-expansion algorithm for network flow problems ⋮ Dynamic constraint and variable aggregation in column generation ⋮ Decomposition theorems for linear programs ⋮ The conditional \(p\)-dispersion problem ⋮ Vector Space Decomposition for Solving Large-Scale Linear Programs ⋮ The minimum mean cycle-canceling algorithm for linear programs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A new version of the improved primal simplex for degenerate linear programs
• 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 data structure for dynamic trees
• An Improved Primal Simplex Algorithm for Degenerate Linear Programs
• Maximal Flow Through a Network
• Decomposition Principle for Linear Programs
• Finding minimum-cost circulations by canceling negative cycles
• A capacity-rounding algorithm for the minimum-cost circulation problem: A dual framework of the Tardos algorithm
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
• An Experimental Study of Minimum Mean Cycle Algorithms
• A Primal Method for Minimal Cost Flows with Applications to the Assignment and Transportation Problems
• Faster parametric shortest path and minimum‐balance algorithms

This page was built for publication: About the minimum mean cycle-canceling algorithm