AN O(N3L) POTENTIAL REDUCTION ALGORITHM FOR LINEAR-PROGRAMMING

We describe a primal-dual potential function for linear programming: [GRAPHICS] where p greater-than-or-equal-to n, x is the primal variable, and s is the dual-slack variable. As a result, we develop an interior point algorithm seeking reductions in the potential function with p = n + square root n. Neither tracing the central path nor using the projective transformation, the algorithm converges to the optimal solution set in O(square root nL) iterations and uses O(n3L) total arithmetic operations. We also suggest a practical approach to implementing the algorithm.