Finding minimum-cost flows by double scaling

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)

zbMATH Keywords

transportation; capacity-scaling; cost- scaling; dynamic tree data structure; excess-scaling; minimum-cost circulations; minimum-cost flow problem

Mathematics Subject Classification ID

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

Minimal-cost network flow problems with variable lower bounds on arc flows, Chips on wafers, or packing rectangles into grids, A double scaling algorithm for the constrained maximum flow problem, An exterior simplex type algorithm for the minimum cost network flow problem, Executability of scenarios in Petri nets, On the computational behavior of a polynomial-time network flow algorithm, A technique for speeding up the solution of the Lagrangean dual, Tight bounds on the number of minimum-mean cycle cancellations and related results, A polynomial time primal network simplex algorithm for minimum cost flows, How to compute least infeasible flows, Algorithms for dense graphs and networks on the random access computer, A new scaling algorithm for the minimum cost network flow problem, A network flow-based method to solve performance cost and makespan open-shop scheduling problems with time-windows, Separation, dimension, and facet algorithms for node flow polyhedra, A NEW APPROACH FOR SOLVING THE MINIMUM COST FLOW PROBLEM WITH INTERVAL AND FUZZY DATA, Parameterized Complexity of Eulerian Deletion Problems

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