Klee-Minty cubes and the central path

We consider a family of LO problems over the n-dimensional Klee-Minty cube and show that the central path may visit all of its vertices in the same order as simplex methods do. This is achieved by carefully adding an exponential number of redundant constraints that forces the central path to take at least 2^n-1 sharp turns. This fact suggests that any feasible path-following IPM will take at least 2^n iterations to solve this problem. This construction exhibits the worst-case iteration-complexity of IPMs. In addition, we discuss some implications for the curvature of the central path.
Joint work with: Antoine Deza, Eissa Nematollahi, Reza Peyghami and Yuriy Zinhenko.