Polynomial-time algorithms for linear programming based only on primal scaling and projected gradients of a potential function

90C60: Abstract computational complexity for mathematical programming problems

90C05: Linear programming

90-08: Computational methods for problems pertaining to operations research and mathematical programming

Related Items

An active-set strategy in an interior point method for linear programming, Convergence behavior of interior-point algorithms, On monotonicity in the scaled potential algorithm for linear programming, A unified approach to interior point algorithms for linear complementarity problems: A summary, Comparative analysis of affine scaling algorithms based on simplifying assumptions, On lower bound updates in primal potential reduction methods for linear programming, A combined phase I-phase II scaled potential algorithm for linear programming, A potential-function reduction algorithm for solving a linear program directly from an infeasible ``warm start, A survey of search directions in interior point methods for linear programming, An \(O(n^ 3L)\) adaptive path following algorithm for a linear complementarity problem, A note on a potential reduction algorithm for LP with simultaneous primal-dual updating, A polynomial method of approximate centers for linear programming, On partial updating in a potential reduction linear programming algorithm of Kojima, Mizuno, and Yoshise, A new polynomial time method for a linear complementarity problem, An \(O(n^ 3 L)\) primal-dual potential reduction algorithm for solving convex quadratic programs, Strict monotonicity and improved complexity in the standard form projective algorithm for linear programming, Updating lower bounds when using Karmarkar's projective algorithm for linear programming, On solution-containing ellipsoids in linear programming, Interior-point algorithms for semi-infinite programming, Convergence property of the Iri-Imai algorithm for some smooth convex programming problems, Potential-reduction methods in mathematical programming, Near boundary behavior of primal-dual potential reduction algorithms for linear programming, Exploiting special structure in a primal-dual path-following algorithm, Potential reduction method for harmonically convex programming, Some variants of the Todd low-complexity algorithm, Large step volumetric potential reduction algorithms for linear programming, New complexity results for the Iri-Imai method, Theoretical convergence of large-step primal-dual interior point algorithms for linear programming, Combining phase I and phase II in a potential reduction algorithm for linear programming, Interior-point methods for linear programming: a review

Cites Work