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

DOI10.1080/10556780500407725MaRDI QIDQ3423600zbMATH OpenOpenAlexFDO

Authors Antoine Deza, Eissa Nematollahi, M. Reza Peyghami, Tamás Terlaky

Publication date 14 February 2007

Published in Optimization Methods \& Software (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1080/10556780500407725

zbMATH Keywords

central pathKlee-Minty cubelinear programming

Mathematics Subject Classification ID

Linear programming (90C05) Interior-point methods (90C51) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• Central path curvature and iteration-complexity for redundant Klee-Minty cubes
• A simpler and tighter redundant Klee-Minty construction
• How good are interior point methods? Klee-Minty cubes tighten iteration-complexity bounds
• A new family of exponential LP problems
• A redundant Klee-Minty construction with all the redundant constraints touching the feasible region

Cites work

• A lower bound on the number of iterations of long-step primal-dual linear programming algorithms
• A new polynomial-time algorithm for linear programming
• How good are interior point methods? Klee-Minty cubes tighten iteration-complexity bounds
• scientific article; zbMATH DE number 1017028 (Why is no real title available?)
• scientific article; zbMATH DE number 964349 (Why is no real title available?)
• Pivot rules for linear programming: A survey on recent theoretical developments

Cited in

(8)

• A redundant Klee-Minty construction with all the redundant constraints touching the feasible region
• How good are interior point methods? Klee-Minty cubes tighten iteration-complexity bounds
• Central path curvature and iteration-complexity for redundant Klee-Minty cubes
• A constraint-reduced variant of Mehrotra's predictor-corrector algorithm
• A linear constrained optimization Benchmark for probabilistic search algorithms: the rotated Klee-Minty problem
• Revisiting degeneracy, strict feasibility, stability, in linear programming
• Multiple faces of optimization. A tribute to Tamás Terlaky on his 70th birthday
• A simpler and tighter redundant Klee-Minty construction

This page was built for publication: The central path visits all the vertices of the Klee–Minty cube

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3423600)