About the minimum mean cycle-canceling algorithm

DOI10.1016/J.DAM.2014.07.005MaRDI QIDQ499347zbMATH OpenOpenAlexFDO

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

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

complexity analysisflow decompositionstrongly polynomial algorithmminimum mean cyclenetwork flow problemresidual network

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Recommendations

• New polynomial-time cycle-canceling algorithms for minimum-cost flows
• Relaxed most negative cycle and most positive cut canceling algorithms for minimum cost flow
• Tight bounds on the number of minimum-mean cycle cancellations and related results
• On dual minimum cost flow algorithms (extended abstract)
• The minimum mean cycle-canceling algorithm for linear programs

Cites work

• scientific article; zbMATH DE number 3148886 (Why is no real title available?)
• scientific article; zbMATH DE number 3174052 (Why is no real title available?)
• scientific article; zbMATH DE number 3718824 (Why is no real title available?)
• A Primal Method for Minimal Cost Flows with Applications to the Assignment and Transportation Problems
• A capacity-rounding algorithm for the minimum-cost circulation problem: A dual framework of the Tardos algorithm
• A characterization of the minimum cycle mean in a digraph
• A data structure for dynamic trees
• A new version of the improved primal simplex for degenerate linear programs
• A strongly polynomial minimum cost circulation algorithm
• An experimental study of minimum mean cycle algorithms
• An improved primal simplex algorithm for degenerate linear programs
• Decomposition Principle for Linear Programs
• Faster parametric shortest path and minimum‐balance algorithms
• Finding minimum-cost circulations by canceling negative cycles
• Maximal Flow Through a Network
• Network flows. Theory, algorithms, and applications.
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
• Tight bounds on the number of minimum-mean cycle cancellations and related results

Cited in

(12)

• Dynamic constraint and variable aggregation in column generation
• Vector Space Decomposition for Solving Large-Scale Linear Programs
• Tight bounds on the number of minimum-mean cycle cancellations and related results
• Smoothed analysis of the minimum-mean cycle canceling algorithm and the network simplex algorithm
• Decomposition theorems for linear programs
• A strongly polynomial contraction-expansion algorithm for network flow problems
• Heterogeneous Multi-resource Allocation with Subset Demand Requests
• scientific article; zbMATH DE number 2219402 (Why is no real title available?)
• A minimum mean cycle cancelling method for nonlinear multicommodity flow problems
• The minimum mean cycle-canceling algorithm for linear programs
• Smoothed analysis of the minimum-mean cycle canceling algorithm and the network simplex algorithm
• The conditional \(p\)-dispersion problem

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q499347)