A Strongly Polynomial Algorithm for Generalized Flow Maximization
Author:
- 1 January 2017
- journal article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Mathematics of Operations Research
- Vol. 42 (1) , 179-211
Abstract
A strongly polynomial algorithm is given for the generalized flow maximization problem. It uses a new variant of the scaling technique called continuous scaling. The main measure of progress is that within a strongly polynomial number of steps, an arc can be identified that must be tight in every dual optimal solution and thus can be contracted. As a consequence of the result, we also obtain a strongly polynomial algorithm for the linear feasibility problem with at most two nonzero entries per column in the constraint matrix.Keywords
All Related Versions
This publication has 30 references indexed in Scilit:
- Fast and simple approximation schemes for generalized flowMathematical Programming, 2002
- A Faster Combinatorial Algorithm for the Generalized Circulation ProblemMathematics of Operations Research, 1996
- New algorithms for generalized network flowsMathematical Programming, 1994
- A Strongly Polynomial Algorithm for a Special Class of Linear ProgramsOperations Research, 1991
- Combinatorial Algorithms for the Generalized Circulation ProblemMathematics of Operations Research, 1991
- Finding minimum-cost circulations by canceling negative cyclesJournal of the ACM, 1989
- Fibonacci heaps and their uses in improved network optimization algorithmsJournal of the ACM, 1987
- On the equivalence of some generalized network problems to pure network problemsMathematical Programming, 1973
- Theoretical Improvements in Algorithmic Efficiency for Network Flow ProblemsJournal of the ACM, 1972
- Linear Programming and Extensions1963