Finding minimum-cost flows by double scaling
Publication:1184348
DOI10.1007/BF01585705zbMath0761.90036WikidataQ59592661 ScholiaQ59592661MaRDI QIDQ1184348
Ravindra K. Ahuja, James B. Orlin, Andrew V. Goldberg, Robert Endre Tarjan
Publication date: 28 June 1992
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
transportation; capacity-scaling; cost- scaling; dynamic tree data structure; excess-scaling; minimum-cost circulations; minimum-cost flow problem
90C35: Programming involving graphs or networks
90C60: Abstract computational complexity for mathematical programming problems
90C08: Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.)
90B10: Deterministic network models in operations research
90-08: Computational methods for problems pertaining to operations research and mathematical programming
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A strongly polynomial minimum cost circulation algorithm
- Scaling algorithms for network problems
- A data structure for dynamic trees
- On a Class of Capacitated Transportation Problems
- A Fast and Simple Algorithm for the Maximum Flow Problem
- Finding Minimum-Cost Circulations by Successive Approximation
- Finding minimum-cost circulations by canceling negative cycles
- On the simplex algorithm for networks and generalized networks
- Self-adjusting binary search trees
- An $O(n\log \log n)$-Time Algorithm for Triangulating a Simple Polygon
- A new approach to the maximum-flow problem
- Improved Time Bounds for the Maximum Flow Problem
- Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
- Faster Scaling Algorithms for Network Problems
- A bad network problem for the simplex method and other minimum cost flow algorithms