Back to Search
Start Over
A Strongly Polynomial Algorithm for Generalized Flow Maximization.
- Source :
- Mathematics of Operations Research; Feb2017, Vol. 42 Issue 1, p179-211, 33p
- Publication Year :
- 2017
-
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. [ABSTRACT FROM AUTHOR]
- Subjects :
- POLYNOMIALS
ALGORITHMS
PROBLEM solving
MATRICES (Mathematics)
MATHEMATICAL analysis
Subjects
Details
- Language :
- English
- ISSN :
- 0364765X
- Volume :
- 42
- Issue :
- 1
- Database :
- Complementary Index
- Journal :
- Mathematics of Operations Research
- Publication Type :
- Academic Journal
- Accession number :
- 121330600
- Full Text :
- https://doi.org/10.1287/moor.2016.0800