Abstract (100 words or less): |  | Refining a recently introduced example that forces the central path to visit all the vertices of the Klee-Minty $n$-cube, we exhibit a nearly worst-case example for path-following interior point methods. Namely, while the theoretical iteration-complexity upper bound is $O(2^{n}n^{\frac{5}{2}})$, we prove that
solving this $n$-dimensional linear optimization problem requires at least $2^n-1$ iterations. |