Journal article
Large step volumetric potential reduction algorithms for linear programming
Annals of operations research, Vol.62(1), pp.521-538
12/1996
DOI: 10.1007/BF02206828
Abstract
We consider the construction of potential reduction algorithms using volumetric, and mixed volumetric — logarithmic, barriers. These are true “large step” methods, where dual updates produce constant-factor reductions in the primal-dual gap. Using a mixed volumetric — logarithmic barrier we obtain an O(~/nmL) iteration algorithm, improving on the best previously known complexity for a large step method. Our results complement those of Vaidya and Atkinson on small step volumetric, and mixed volumetric — logarithmic, barrier function algorithms. We also obtain simplified proofs of fundamental properties of the volumetric barrier, originally due to Vaidya.
Details
- Title: Subtitle
- Large step volumetric potential reduction algorithms for linear programming
- Creators
- Kurt M. Anstreicher - University of Iowa
- Resource Type
- Journal article
- Publication Details
- Annals of operations research, Vol.62(1), pp.521-538
- DOI
- 10.1007/BF02206828
- ISSN
- 0254-5330
- eISSN
- 1572-9338
- Language
- English
- Date published
- 12/1996
- Academic Unit
- Business Analytics; Industrial and Systems Engineering; Computer Science
- Record Identifier
- 9984380581302771
Metrics
6 Record Views