Central Path Curvature and Iteration-Complexity for Redundant Klee—Minty Cubes
From MaRDI portal
Publication:3565464
DOI10.1007/978-0-387-75714-8_7zbMath1189.90098MaRDI QIDQ3565464
Tamás Terlaky, Antoine Deza, Yuriy Zinchenko
Publication date: 4 June 2010
Published in: Advances in Mechanics and Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-0-387-75714-8_7
65K05: Numerical mathematical programming methods
52B12: Special polytopes (linear programming, centrally symmetric, etc.)
90C05: Linear programming
Related Items
Polytopes and arrangements: diameter and curvature, A simpler and tighter redundant Klee-Minty construction, A continuous \(d\)-step conjecture for polytopes
Cites Work
- A strong bound on the integral of the central path curvature and its relationship with the iteration-complexity of primal-dual path-following LP algorithms
- Polytopes and arrangements: diameter and curvature
- On the complexity of following the central path of linear programs by linear extrapolation. II
- Estimating the complexity of a class of path-following methods for solving linear programs by curvature integrals
- A primal-dual interior point method whose running time depends only on the constraint matrix
- Computational techniques of the simplex method
- On the Riemannian geometry defined by self-concordant barriers and interior-point methods.
- A lower bound on the number of iterations of long-step primal-dual linear programming algorithms
- How good are interior point methods? Klee-Minty cubes tighten iteration-complexity bounds
- On the curvature of the central path of linear programming theory
- The central path visits all the vertices of the Klee–Minty cube
- Boundary Behavior of Interior Point Algorithms in Linear Programming
- Presolve Analysis of Linear Programs Prior to Applying an Interior Point Method
- NEWTON FLOW AND INTERIOR POINT METHODS IN LINEAR PROGRAMMING
- Interior Point Methods for Linear Optimization
