The minimum cost flow problem: A unifying approach to dual algorithms and a new tree-search algorithm

DOI10.1007/BF02591772zbMath0501.90035MaRDI QIDQ3967334

Refael Hassin

Publication date: 1983

Published in: Mathematical Programming (Search for Journal in Brave)

zbMATH Keywords

primal-dual algorithmdual algorithmsdirected networkminimum cost flow problemminimum cost network flowtree-search algorithm

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Numerical mathematical programming methods (65K05) Deterministic network models in operations research (90B10)

Related Items

Computing maximum mean cuts, How to compute least infeasible flows, An \(O(mn \log (nU))\) time algorithm to solve the feasibility problem, A dual algorithm for submodular flow problems, Dijkstra's algorithm and L-concave function maximization, Algorithms for the minimum cost circulation problem based on maximizing the mean improvement, Two strongly polynomial cut cancelling algorithms for minimum cost network flow, Minimum ratio canceling in oracle polynomial for linear programming, but not strongly polynomial, even for networks, A new approach for computing a most positive cut using the minimum flow algorithms, A new algorithm for solving the feasibility problem of a network flow, Exact bounds for steepest descent algorithms of $L$-convex function minimization, Discrete Convex Functions on Graphs and Their Algorithmic Applications, Tight bounds on the number of minimum-mean cycle cancellations and related results

Cites Work

• An Out-of-Kilter Method for Minimal-Cost Flow Problems
• A Computation Study on Start Procedures, Basis Change Criteria, and Solution Algorithms for Transportation Problems
• A note on the primal-dual and out-of-kilter algorithms for network optimization problems
• Implementation and computational comparisons of primal, dual and primal-dual computer codes for minimum cost network flow problems
• A bad network problem for the simplex method and other minimum cost flow algorithms
• A Primal Method for Minimal Cost Flows with Applications to the Assignment and Transportation Problems
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item