Klee-Minty polytope

From Glossary

Jump to: navigation, search


This is an example to show that the elementary simplex method does not have polynomial time complexity. The polytope is

LaTeX: 
\left\{ x : 
\left(\sum_{i=1}^{k-1} 2^{k-i+1} x_i \right) + x_k \le 5^k, 
</p>
<pre>               \; \mbox{ for } k = 1, 2, \ldots, n, \; x \ge 0 \right\}
</pre>
<p>

Maximizing

LaTeX: 
\sum_{i=1}^n 2^{n-i} x_i

over this polytope shows the exponential complexity.


Views
Personal tools