Large step volumetric potential reduction algorithms for linear programming

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(root 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.