# KleeâMinty cube Information

*https://en.wikipedia.org/wiki/KleeâMinty_cube*

The **KleeâMinty cube** or **KleeâMinty polytope** (named after
Victor Klee and
George J. Minty) is a
unit
hypercube of variable
dimension whose corners have been perturbed. Klee and Minty demonstrated that
George Dantzig's
simplex algorithm has poor worst-case performance when initialized at one corner of their "squashed cube". On the three-dimensional version, the
simplex algorithm and the
criss-cross algorithm visit all 8 corners in the worst case.

In particular, many optimization
algorithms for
linear optimization exhibit poor performance when applied to the KleeâMinty cube. In 1973 Klee and Minty showed that Dantzig's
simplex algorithm was not a
polynomial-time algorithm when applied to their cube.^{
[1]} Later, modifications of the KleeâMinty cube have shown poor behavior both for other
basis-
exchange pivoting algorithms and also for interior-point algorithms.^{
[2]}

## Description of the cube

The KleeâMinty cube was originally specified with a parameterized system of linear inequalities, with the dimension as the parameter. When the dimension is two, the "cube" is a squashed square. When the dimension is three, the "cube" is a squashed cube. Illustrations of the "cube" have appeared besides algebraic descriptions.^{
[2]}^{
[3]}

The KleeâMinty polytope is given by^{
[4]}

This has *D* variables, *D* constraints other than the *D* non-negativity constraints, and 2^{D} vertices, just as a *D*-dimensional
hypercube does. If the objective function to be maximized is

and if the initial vertex for the simplex algorithm is the origin, then the algorithm as formulated by Dantzig visits all 2^{D} vertices, finally reaching the optimal vertex

## Computational complexity

The KleeâMinty cube has been used to analyze the performance of many algorithms, both in the worst case and on average. The
time complexity of an
algorithm counts the number of
arithmetic operations sufficient for the algorithm to solve the problem. For example,
Gaussian elimination requires on the
order of* D*^{3} operations, and so it is said to have polynomial time-complexity, because its complexity is bounded by a
cubic polynomial. There are examples of algorithms that do not have polynomial-time complexity. For example, a generalization of Gaussian elimination called
Buchberger's algorithm has for its complexity an exponential function of the problem data (the
degree of the polynomials and the number of variables of the
multivariate polynomials). Because exponential functions eventually grow much faster than polynomial functions, an exponential complexity implies that an algorithm has slow performance on large problems.

### Worst case

In mathematical optimization, the KleeâMinty cube is an example that shows the
worst-case
computational
complexity of many
algorithms of
linear optimization. It is a deformed
cube with exactly 2^{D} corners in
dimension *D*. Klee and Minty showed that
Dantzig's
simplex algorithm visits all corners of a (perturbed)
cube in dimension *D* in the
worst case.^{
[1]}^{
[5]}^{
[6]}

Modifications of the KleeâMinty construction showed similar exponential
time complexity for other pivoting rules of simplex type, which maintain primal feasibility, such as
Bland's rule.^{
[7]}^{
[8]}^{
[9]} Another modification showed that the
criss-cross algorithm, which does not maintain primal feasibility, also visits all the corners of a modified KleeâMinty cube.^{
[6]}^{
[10]}^{
[11]} Like the simplex algorithm, the criss-cross algorithm visits all 8 corners of the three-dimensional cube in the worst case.

#### Path-following algorithms

Further modifications of the KleeâMinty cube have shown poor performance of
central-path
âfollowing algorithms for linear optimization, in that the central path comes arbitrarily close to each of the corners of a cube. This "vertex-stalking" performance is surprising, because such path-following algorithms have polynomial-time complexity for linear optimization.^{
[2]}^{
[12]}

### Average case

The KleeâMinty cube has also inspired research on
average-case complexity. When eligible pivots are made randomly (and not by the rule of steepest descent), Dantzig's simplex algorithm needs
on average
quadratically many steps (
on the order of O(*D*^{2}).^{
[3]}
Standard variants of the simplex algorithm takes on average *D* steps for a cube.^{
[a]} When it is initialized at a random corner of the cube, the criss-cross algorithm visits only *D* additional corners, however, according to a 1994 paper by Fukuda and Namiki.^{
[14]}^{
[15]} Both the simplex algorithm and the criss-cross algorithm visit exactly 3 additional corners of the three-dimensional cube on average.

## See also

## Notes

**^**More generally, for the simplex algorithm, the expected number of steps is proportional to*D*for linear-programming problems that are randomly drawn from the Euclidean unit sphere, as proved by Borgwardt^{ [13]}and by Smale.^{[ citation needed]}

- ^
^{a}^{b}Klee & Minty (1972) - ^
^{a}^{b}^{c}Deza, Nematollahi & Terlaky (2008) - ^
^{a}^{b}Gartner & Ziegler (1994) **^**Greenberg, Harvey J.,*Klee-Minty Polytope Shows Exponential Time Complexity of Simplex Method*University of Colorado at Denver (1997) PDF download**^**Murty (1983, 14.2 Worst-case computational complexity, pp. 434â437)- ^
^{a}^{b}Terlaky & Zhang (1993) **^**Bland, Robert G. (May 1977). "New finite pivoting rules for the simplex method".*Mathematics of Operations Research*.**2**(2): 103â107. doi: 10.1287/moor.2.2.103. JSTOR 3689647. MR 0459599.**^**Murty (1983, Chapter 10.5, pp. 331â333; problem 14.8, p. 439) describes Bland's rule.**^**Murty (1983, Problem 14.3, p. 438; problem 14.8, p. 439) describes the worst-case complexity of Bland's rule.**^**Roos (1990)**^**Fukuda & Terlaky (1997)**^**Megiddo & Shub (1989)**^**Borgwardt, Karl-Heinz (1987).*The simplex method: A probabilistic analysis*. Algorithms and Combinatorics (Study and Research Texts). Vol. 1. Berlin: Springer-Verlag. ISBN 978-3-540-17096-9. MR 0868467.**^**Fukuda & Namiki (1994, p. 367)**^**Fukuda & Terlaky (1997, p. 385)

## References

- Deza, Antoine; Nematollahi, Eissa; Terlaky, TamĂĄs (May 2008).
"How good are interior point methods? KleeâMinty cubes tighten iteration-complexity bounds" (PDF).
*Mathematical Programming*.**113**(1): 1â14. CiteSeerX 10.1.1.214.111. doi: 10.1007/s10107-006-0044-x. MR 2367063. -
Fukuda, Komei; Namiki, Makoto (March 1994). "On extremal behaviors of Murty's least index method".
*Mathematical Programming*.**64**(1): 365â370. doi: 10.1007/BF01582581. MR 1286455. -
Fukuda, Komei;
Terlaky, TamĂĄs (1997). Thomas M. Liebling; Dominique de Werra (eds.). "Criss-cross methods: A fresh view on pivot algorithms".
*Mathematical Programming, Series B*.**79**(Papers from the 16th International Symposium on Mathematical Programming held in Lausanne, 1997): 369â395. CiteSeerX 10.1.1.36.9373. doi: 10.1007/BF02614325. MR 1464775. Postscript preprint. - Gartner, B.;
Ziegler, G. M. (1994).
*Randomized simplex algorithms on Klee-Minty cubes*.*Foundations of Computer Science, Annual IEEE Symposium on*. IEEE. pp. 502â510. CiteSeerX 10.1.1.24.1405. doi: 10.1109/SFCS.1994.365741. ISBN 978-0-8186-6580-6. -
Klee, Victor;
Minty, George J. (1972). "How good is the simplex algorithm?". In Shisha, Oved (ed.).
*Inequalities III (Proceedings of the Third Symposium on Inequalities held at the University of California, Los Angeles, Calif., September 1â9, 1969, dedicated to the memory of Theodore S. Motzkin)*. New York-London: Academic Press. pp. 159â175. MR 0332165. -
Megiddo, Nimrod;
Shub, Michael (February 1989). "Boundary Behavior of Interior Point Algorithms in Linear Programming".
*Mathematics of Operations Research*.**14**(1): 97â146. CiteSeerX 10.1.1.80.184. doi: 10.1287/moor.14.1.97. JSTOR 3689840. MR 0984561. -
Murty, Katta G. (1983).
*Linear programming*. New York: John Wiley & Sons. pp. xix+482. ISBN 978-0-471-09725-9. MR 0720547. - Roos, C. (1990). "An exponential example for Terlaky's pivoting rule for the criss-cross simplex method".
*Mathematical Programming*. Series A.**46**(1): 79â84. doi: 10.1007/BF01585729. MR 1045573. - Terlaky, TamĂĄs; Zhang, Shu Zhong (1993). "Pivot rules for linear programming: A Survey on recent theoretical developments".
*Annals of Operations Research*.**46**(Degeneracy in optimization problems, number 1): 203â233. CiteSeerX 10.1.1.36.7658. doi: 10.1007/BF02096264. ISSN 0254-5330. MR 1260019.

## External links

### Algebraic description with illustration

The first two links have both an algebraic construction and a picture of a three-dimensional KleeâMinty cube:

- Deza, Antoine; Nematollahi, Eissa; Terlaky, TamĂĄs (May 2008).
"How good are interior point methods? KleeâMinty cubes tighten iteration-complexity bounds" (PDF).
*Mathematical Programming*.**113**(1): 1â14. CiteSeerX 10.1.1.214.111. doi: 10.1007/s10107-006-0044-x. MR 2367063. - Gartner, B.;
Ziegler, G. M. (1994).
*Randomized simplex algorithms on Klee-Minty cubes*.*Foundations of Computer Science, Annual IEEE Symposium on*. IEEE. pp. 502â510. CiteSeerX 10.1.1.24.1405. doi: 10.1109/SFCS.1994.365741. ISBN 978-0-8186-6580-6. IEEE mis-spells the name "GĂ€rnter" as "Gartner" (sic.).

### Pictures with no linear system

- Articles of E. Nematollahi, which discuss the Klee-Minty cube with illustrations.
- A picture of a Klee-Minty cube showing a simplex-algorithm path (automatic translation of German) by GĂŒnter Ziegler. The picture in the second half of the page.