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

DOI10.1007/BF01580882MaRDI QIDQ3731344zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• A strongly polynomial minimum cost circulation algorithm
• scientific article; zbMATH DE number 3900474
• A Faster Strongly Polynomial Minimum Cost Flow Algorithm
• Finding minimum-cost circulations by canceling negative cycles
• On dual minimum cost flow algorithms

Cites work

• scientific article; zbMATH DE number 3643026 (Why is no real title available?)
• scientific article; zbMATH DE number 3174052 (Why is no real title available?)
• scientific article; zbMATH DE number 3900474 (Why is no real title available?)
• scientific article; zbMATH DE number 3580570 (Why is no real title available?)
• scientific article; zbMATH DE number 3349645 (Why is no real title available?)
• A Primal-Dual Algorithm for Submodular Flows
• Network flow, transportation and scheduling. Theory and algorithms
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems

Cited in

(17)

• A survey on exact algorithms for the maximum flow and minimum‐cost flow problems
• An update-and-stabilize framework for the minimum-norm-point problem
• A fully combinatorial algorithm for submodular function minimization.
• Algorithms for the minimum cost circulation problem based on maximizing the mean improvement
• Minimum-cost flow algorithms: an experimental evaluation
• scientific article; zbMATH DE number 3900474 (Why is no real title available?)
• Mathematical Considerations on the Relationship between the Ordering of players and Winning Probability in Certain Types of Team Sports
• A dual version of Tardos's algorithm for linear programming
• Personal reminiscence: combinatorial and discrete optimization problems in which I have been interested
• The minimal average cost flow problem
• 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 strongly polynomial minimum cost circulation algorithm
• An application of simultaneous diophantine approximation in combinatorial optimization
• An O (n ² (m + N log n )log n ) min-cost flow algorithm
• An update-and-stabilize framework for the minimum-norm-point problem
• About the minimum mean cycle-canceling algorithm

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

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