Finding minimum-cost flows by double scaling

DOI10.1007/BF01585705zbMath0761.90036OpenAlexW2075322358WikidataQ59592661 ScholiaQ59592661MaRDI QIDQ1184348

Ravindra K. Ahuja, Andrew V. Goldberg, James B. Orlin, Robert Endre Tarjan

Publication date: 28 June 1992

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

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

zbMATH Keywords

transportationcapacity-scalingcost- scalingdynamic tree data structureexcess-scalingminimum-cost circulationsminimum-cost flow problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08) Deterministic network models in operations research (90B10) Computational methods for problems pertaining to operations research and mathematical programming (90-08)

Related Items

A fast cost scaling algorithm for submodular flow, 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 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 Simple Efficient Interior Point Method for Min-Cost Flow, Minimum-cost flow algorithms: an experimental evaluation, Finding paths with minimum shared edges, \textsc{Hide} \& \textsc{Seek}: privacy-preserving rebalancing on payment channel networks, DEA‐based centralized resource allocation with network flows, Flow constrained minimum cost flow problem, Finding optimal non-datapath caching strategies via network flow, Minimum-cost flows in unit-capacity networks, A survey on exact algorithms for the maximum flow and minimum‐cost flow problems, Minimal-cost network flow problems with variable lower bounds on arc flows, An \(O(m(m+n\log {n})\log(nC))\)-time algorithm to solve the minimum cost tension problem, Unnamed Item, Parameterized complexity of Eulerian deletion problems, On the transformation mechanism for formulating a multiproduct two-layer supply chain network design problem as a network flow model, A new scaling algorithm for the minimum cost network flow problem, A double scaling algorithm for the constrained maximum flow problem, A NEW APPROACH FOR SOLVING THE MINIMUM COST FLOW PROBLEM WITH INTERVAL AND FUZZY DATA, On the computational behavior of a polynomial-time network flow algorithm, An exterior simplex type algorithm for the minimum cost network flow problem, Chips on wafers, or packing rectangles into grids, Executability of scenarios in Petri nets, Parameterized Complexity of Eulerian Deletion Problems, A technique for speeding up the solution of the Lagrangean dual, Tight bounds on the number of minimum-mean cycle cancellations and related results

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