A capacity-rounding algorithm for the minimum-cost circulation problem: A dual framework of the Tardos algorithm

DOI10.1007/BF01580882zbMath0597.90029OpenAlexW2053760675MaRDI QIDQ3731344

Satoru Fujishige

Publication date: 1986

Published in: Mathematical Programming (Search for Journal in Brave)

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

zbMATH Keywords

computational complexityshortest pathmaximum flowstrongly polynomial algorithmcapacity-rounding algorithmminimum-cost circulation problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Deterministic network models in operations research (90B10)

Related Items (11)

An application of simultaneous diophantine approximation in combinatorial optimization ⋮ Minimum-cost flow algorithms: an experimental evaluation ⋮ The minimal average cost flow problem ⋮ Personal reminiscence: combinatorial and discrete optimization problems in which I have been interested ⋮ An update-and-stabilize framework for the minimum-norm-point problem ⋮ A survey on exact algorithms for the maximum flow and minimum‐cost flow problems ⋮ About the minimum mean cycle-canceling algorithm ⋮ Two strongly polynomial cut cancelling algorithms for minimum cost network flow ⋮ A Push/Relabel framework for submodular flows and its definement for 0-1 submodular flows ⋮ A dual version of Tardos's algorithm for linear programming ⋮ A fully combinatorial algorithm for submodular function minimization.

Cites Work

• Network flow, transportation and scheduling. Theory and algorithms
• A Primal-Dual Algorithm for Submodular Flows
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A capacity-rounding algorithm for the minimum-cost circulation problem: A dual framework of the Tardos algorithm