Name
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
<img src="/fulltext-image.asp?format=htmlnonpaginated&src=YLQ578T431641661_html\10479_2005_Article_BF02206828_TeX2GIFIE1.gif" border="0" alt="
$$O(\sqrt {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. |
Year | DOI | Venue |
|---|---|---|
1996 | 10.1007/BF02206828 | Annals of Operations Research |
Keywords | Field | DocType |
interior algorithm,linear programming,potential reduction,volumetric barrier.,Linear programming,volumetric barrier | Mathematical optimization,Mathematical analysis,Algorithm,Mathematical proof,Linear programming,Logarithm,Mathematics | Journal |
Volume | Issue | ISSN |
62 | 1 | 1572-9338 |
Citations | PageRank | References |
6 | 0.67 | 8 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Kurt M. Anstreicher | 1 | 633 | 86.40 |