How good are interior point methods? Klee-Minty cubes tighten iteration-complexity bounds
DOI10.1007/S10107-006-0044-XzbMATH Open1176.90394OpenAlexW2056369327MaRDI QIDQ2476985FDOQ2476985
Authors: Antoine Deza, Eissa Nematollahi, Tamás Terlaky 
Publication date: 12 March 2008
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10107-006-0044-x
Recommendations
- Central path curvature and iteration-complexity for redundant Klee-Minty cubes
- The central path visits all the vertices of the Klee–Minty cube
- What is the worst case behavior of the simplex algorithm?
- The iteration-complexity upper bound for the Mizuno-Todd-Ye predictor-corrector algorithm is tight
- A simpler and tighter redundant Klee-Minty construction
Linear programming (90C05) Interior-point methods (90C51) Special polytopes (linear programming, centrally symmetric, etc.) (52B12)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- A new polynomial-time algorithm for linear programming
- Title not available (Why is that?)
- Title not available (Why is that?)
- A primal-dual interior point method whose running time depends only on the constraint matrix
- Polytopes and arrangements: diameter and curvature
- Pivot rules for linear programming: A survey on recent theoretical developments
- The central path visits all the vertices of the Klee–Minty cube
- Boundary Behavior of Interior Point Algorithms in Linear Programming
- A lower bound on the number of iterations of long-step primal-dual linear programming algorithms
Cited In (14)
- Smoothed analysis of condition numbers and complexity implications for linear programming
- The iteration-complexity upper bound for the Mizuno-Todd-Ye predictor-corrector algorithm is tight
- A new family of exponential LP problems
- On the volumetric path
- Polytope-based computation of polynomial ranges
- Central path curvature and iteration-complexity for redundant Klee-Minty cubes
- A redundant Klee-Minty construction with all the redundant constraints touching the feasible region
- Interior Point Methods for Nonlinear Optimization
- A linear constrained optimization Benchmark for probabilistic search algorithms: the rotated Klee-Minty problem
- The Chebyshev center as an alternative to the analytic center in the feasibility pump
- Revisiting degeneracy, strict feasibility, stability, in linear programming
- A simpler and tighter redundant Klee-Minty construction
- The central path visits all the vertices of the Klee–Minty cube
- On semidefinite least squares and minimal unsatisfiability
This page was built for publication: How good are interior point methods? Klee-Minty cubes tighten iteration-complexity bounds
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2476985)
