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

DOI10.1007/BF01580882zbMATH Open0597.90029OpenAlexW2053760675MaRDI QIDQ3731344FDOQ3731344

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

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

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)

Cites Work

• Title not available (Why is that?)
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• A Primal-Dual Algorithm for Submodular Flows
• Title not available (Why is that?)
• Network flow, transportation and scheduling. Theory and algorithms

Cited In (16)

• A survey on exact algorithms for the maximum flow and minimum‐cost flow problems
• 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
• Title not available (Why is that?)
• Mathematical Considerations on the Relationship between the Ordering of players and Winning Probability in Certain Types of Team Sports
• Personal reminiscence: combinatorial and discrete optimization problems in which I have been interested
• A dual version of Tardos's algorithm for linear programming
• The minimal average cost flow problem
• A Push/Relabel framework for submodular flows and its definement for 0-1 submodular flows
• Two strongly polynomial cut cancelling algorithms for minimum cost network flow
• An O (n ² (m + N log n )log n ) min-cost flow algorithm
• A strongly polynomial minimum cost circulation algorithm
• An application of simultaneous diophantine approximation in combinatorial optimization
• 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)