A lower bound on the number of iterations of long-step primal-dual linear programming algorithms
From MaRDI portal
Publication:1915913
DOI10.1007/BF02206818zbMath0848.90092MaRDI QIDQ1915913
Publication date: 1 July 1996
Published in: Annals of Operations Research (Search for Journal in Brave)
interior-point algorithmsduality gaplower boundpath-followingpolynomialityprimal-dual affine-scaling method
Related Items
Log-Barrier Interior Point Methods Are Not Strongly Polynomial, Smoothed analysis of condition numbers and complexity implications for linear programming, A simpler and tighter redundant Klee-Minty construction, An infeasible interior-point algorithm with full-Newton step for linear optimization, Central Path Curvature and Iteration-Complexity for Redundant Klee—Minty Cubes, How good are interior point methods? Klee-Minty cubes tighten iteration-complexity bounds, SimplifiedO(nL) infeasible interior-point algorithm for linear optimization using full-Newton steps, The central path visits all the vertices of the Klee–Minty cube
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A new polynomial-time algorithm for linear programming
- Computational experience with a primal-dual interior point method for linear programming
- Interior path following primal-dual algorithms. I: Linear programming
- A polynomial-time algorithm for a class of linear complementarity problems
- An \(O(\sqrt n L)\) iteration potential reduction algorithm for linear complementarity problems
- On the complexity of following the central path of linear programs by linear extrapolation. II
- A primal-dual infeasible-interior-point algorithm for linear programming
- Finding an interior point in the optimal face of linear programs
- On the number of iterations of Karmarkar's algorithm for linear programming
- Computational experience with a globally convergent primal-dual predictor-corrector algorithm for linear programming
- Path-Following Methods for Linear Programming
- On the Performance of Karmarkar’s Algorithm over a Sequence of Iterations
- On Adaptive-Step Primal-Dual Interior-Point Algorithms for Linear Programming
- Toward Probabilistic Analysis of Interior-Point Algorithms for Linear Programming
- A Complexity Analysis for Interior-Point Algorithms Based on Karmarkar’s Potential Function
