Large step volumetric potential reduction algorithms for linear programming

The paper considers 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 the paper obtains an iteration algorithm, improving on the best previously known complexity for a large step method. The present results complement those of Vaidya and Atkinson on small step volumetric, and mixed volumetric-logarithmic, barrier function algorithms. The paper also obtains simplified proofs of fundamental properties of the volumetric barrier, originally due to Viadya.