j*********3
发帖数: 32 | 1 Does anybody know why Simplex method is exponential? Could you give me the
proof? Thank you .... | j*********3
发帖数: 32 | 2 Ding bymyself
【在 j*********3 的大作中提到】
: Does anybody know why Simplex method is exponential? Could you give me the
: proof? Thank you ....
| c******a
发帖数: 6951 | 3 V. Klee and G.J. Minty. "How Good is the Simplex Algorithm?" In O. Shisha,
editor, Inequalities, III, pages 159–175. Academic Press, New York, NY,
1972
Simplex pivot rules visit all 2^n vertices before arriving at the optimal
point in an example in which the polytope P is a distortion of an n-
dimensional cube. This shows that the upper bound complexity of the
algorithm is exponential time. This is the worst case. The simplex method is
remarkably efficient in practice.
【在 j*********3 的大作中提到】
: Does anybody know why Simplex method is exponential? Could you give me the
: proof? Thank you ....
|
|
