Polynomial-time algorithms for linear programming based only on primal scaling and projected gradients of a potential function
From MaRDI portal
Publication:1177228
DOI10.1007/BF01586933zbMath0743.90073OpenAlexW1996309927MaRDI QIDQ1177228
Publication date: 26 June 1992
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01586933
Abstract computational complexity for mathematical programming problems (90C60) Linear programming (90C05) Computational methods for problems pertaining to operations research and mathematical programming (90-08)
Related Items
Interior-point algorithms for semi-infinite programming, Convergence property of the Iri-Imai algorithm for some smooth convex programming problems, 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, Potential reduction method for harmonically convex programming, A modified homogeneous potential reduction algorithm for solving the monotone semidefinite linear complementarity problem, Potential-reduction methods in mathematical 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, 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, An active-set strategy in an interior point method for linear programming, Convergence behavior of interior-point algorithms, 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, Near boundary behavior of primal-dual potential reduction algorithms for linear programming, Exploiting special structure in a primal-dual path-following algorithm, Projective re-normalization for improving the behavior of a homogeneous conic linear system, On monotonicity in the scaled potential algorithm for linear programming, 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 methods for linear programming: a review
Cites Work
- A monotonic projective algorithm for fractional linear programming
- A new polynomial-time algorithm for linear programming
- A standard form variant, and safeguarded linesearch, for the modified Karmarkar algorithm
- An algorithm for linear programming which requires \(O(((m+n)n^ 2+(m+n)^{1.5}n)L)\) arithmetic operations
- Introduction: New approaches to linear programming
- An extension of Karmarkar's algorithm for linear programming using dual variables
- A polynomial-time algorithm, based on Newton's method, for linear programming
- A Centered Projective Algorithm for Linear Programming
- A variant of Karmarkar's linear programming algorithm for problems in standard form
- The Nonlinear Geometry of Linear Programming. II Legendre Transform Coordinates and Central Trajectories
