A simpler and tighter redundant Klee-Minty construction

DOI10.1007/s11590-007-0068-zzbMath1279.90112OpenAlexW2066043589MaRDI QIDQ941030

Eissa Nematollahi, Tamás Terlaky

Publication date: 4 September 2008

Published in: Optimization Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s11590-007-0068-z

zbMATH Keywords

linear programminginterior point methodscentral pathworst-case iteration complexityKlee-Minty example

Mathematics Subject Classification ID

Linear programming (90C05) Interior-point methods (90C51)

Related Items (2)

An \(O(\sqrt nL)\) iteration primal-dual second-order corrector algorithm for linear programming ⋮ A redundant Klee-Minty construction with all the redundant constraints touching the feasible region

Cites Work

• Unnamed Item
• Unnamed Item
• A new polynomial-time algorithm for linear programming
• Pivot rules for linear programming: A survey on recent theoretical developments
• A primal-dual interior point method whose running time depends only on the constraint matrix
• 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
• The central path visits all the vertices of the Klee–Minty cube
• Central Path Curvature and Iteration-Complexity for Redundant Klee—Minty Cubes

This page was built for publication: A simpler and tighter redundant Klee-Minty construction