Long steps in an \(O(n^ 3L)\) algorithm for linear programming
From MaRDI portal
Publication:1196717
DOI10.1007/BF01586053zbMath0783.90066MaRDI QIDQ1196717
Kurt M. Anstreicher, Robert A. Bosch
Publication date: 16 January 1993
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
65K05: Numerical mathematical programming methods
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
Convergence behavior of interior-point algorithms, Comparative analysis of affine scaling algorithms based on simplifying assumptions, On lower bound updates in primal potential reduction methods for linear programming, 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 polynomial method of approximate centers for linear programming, On partial updating in a potential reduction linear programming algorithm of Kojima, Mizuno, and Yoshise, An interior point method, based on rank-1 updates, 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, Near boundary behavior of primal-dual potential reduction algorithms for linear programming
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A monotonic projective algorithm for fractional linear programming
- A modification of Karmarkar's linear programming algorithm
- A new polynomial-time algorithm for linear programming
- An \(O(n^ 3L)\) potential reduction 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
- Computing Karmarkar projections quickly
- A polynomial-time algorithm, based on Newton's method, for linear programming
- Conical projection algorithms for linear programming
- Interior path following primal-dual algorithms. I: Linear programming
- Polynomial affine algorithms for linear programming
- A variation on Karmarkar’s algorithm for solving linear programming problems
- A Polynomial-Time Primal-Dual Affine Scaling Algorithm for Linear and Convex Quadratic Programming and Its Power Series Extension
- A Centered Projective Algorithm for Linear Programming
- A variant of Karmarkar's linear programming algorithm for problems in standard form
- Recovering optimal dual solutions in Karmarkar's polynomial algorithm for linear programming
- The Nonlinear Geometry of Linear Programming. II Legendre Transform Coordinates and Central Trajectories
- Boundary Behavior of Interior Point Algorithms in Linear Programming
- Large Step Path-Following Methods for Linear Programming, Part II: Potential Reduction Method