The central path visits all the vertices of the Klee–Minty cube

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

zbMATH Keywords

linear programmingcentral pathKlee-Minty cube

Mathematics Subject Classification ID

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