The central path visits all the vertices of the Klee–Minty cube
From MaRDI portal
Publication:3423600
DOI10.1080/10556780500407725zbMath1112.90047OpenAlexW2155630828MaRDI QIDQ3423600
Antoine Deza, M. Reza Peyghami, Tamás Terlaky, Eissa Nematollahi
Publication date: 14 February 2007
Published in: Optimization Methods and Software (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1080/10556780500407725
Abstract computational complexity for mathematical programming problems (90C60) Linear programming (90C05) Interior-point methods (90C51)
Related Items
A linear constrained optimization Benchmark for probabilistic search algorithms: the rotated Klee-Minty problem, Revisiting degeneracy, strict feasibility, stability, in linear programming, A constraint-reduced variant of Mehrotra's predictor-corrector algorithm, A simpler and tighter redundant Klee-Minty construction, Central Path Curvature and Iteration-Complexity for Redundant Klee—Minty Cubes, How good are interior point methods? Klee-Minty cubes tighten iteration-complexity bounds, A redundant Klee-Minty construction with all the redundant constraints touching the feasible region
Cites Work
- A new polynomial-time algorithm for linear programming
- Pivot rules for linear programming: A survey on recent theoretical developments
- 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
- Unnamed Item
- Unnamed Item
