The central path visits all the vertices of the Klee–Minty cube
- 16 August 2006
- journal article
- research article
- Published by Taylor & Francis in Optimization Methods and Software
- Vol. 21 (5) , 851-865
Abstract
The Klee–Minty cube is a well-known worst-case example for which the simplex method takes an exponential number of iterations as the algorithm visits all the 2 n vertices of the n-dimensional cube. While such behaviour is excluded by polynomial interior point methods, we show that, by adding an exponential number of redundant inequalities, the central path can be bent along the edges of the Klee–Minty cube. More precisely, for an arbitrarily small δ, the central path takes 2 n −2 turns as it passes through the δ-neighbourhood of all the vertices of the Klee–Minty cube in the same order as the simplex method does.Keywords
This publication has 5 references indexed in Scilit:
- How good are interior point methods? Klee–Minty cubes tighten iteration-complexity boundsMathematical Programming, 2006
- Primal-Dual Interior-Point Methods1997
- A lower bound on the number of iterations of long-step primal-dual linear programming algorithmsAnnals of Operations Research, 1996
- Pivot rules for linear programming: A survey on recent theoretical developmentsAnnals of Operations Research, 1993
- A new polynomial-time algorithm for linear programmingCombinatorica, 1984