How good are interior point methods?
Klee-Minty cubes tighten iteration-complexity bounds

by Tamas Terlaky

By adding redundant inequalities the central path can be forced to visit any
small neighborhood of all the vertices ofÊthe Klee-Minty cube, in the same order as 
simplex methods do.  A careful refinement and analysis of the example
over the Klee-Minty $n$-cube allows to exhibit a nearly worst-case example for 
path-following interior point methods, i.e., while the theoretical
iteration-complexity upper bound for IPMs is $O(n^{\frac{5}{2}}2^{n})$, 
we prove that solving this $n$-dimensional linear optimization problem 
requires at least $2^n-1$ iterations.

(joint work with Antoine Deza and Eissa Nematollahi)