
The Central Path Visits all the Vertices of the KleeMinty Cube
Mohammad Reza Peyghami Sharif University of Technology 

Abstract:
The KleeMinty cube is a wellknown 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 a behavior is excluded by polynomial interior
point methods, we show that, by adding an exponential number of
redundant inequalities, the central path can be bended along the
edges of the KleeMinty cube. More precisely, for an arbitrary
small $\delta$, starting from the $\delta$neighborhood of a
vertex adjacent to the optimal solution, the central path takes
$2^{n}2$ turns as it passes through the $\delta$neighborhood of
all the vertices of the cube before converging to the optimal
solution. In other words, central pathfollowing interior point
methods visit the neighborhood of all the vertices of the
KleeMinty cube in the same order as the simplex method visits its
vertices.
Information:
Date:  Jan. 20, 2005, 13:0015:00 
Place:  School of Mathematics, Niavaran Bldg., Niavaran Square, Tehran, Iran 

 
