HOW GOOD IS THE SIMPLEX ALGORITHM

Victor L. Klee, George J. Minty · 1970

Abstract : By constructing long 'increasing' paths on appropriate convex polytopes, It is shown that the simplex algorithm for linear programs (at least with its most commonly used pivot rule) is not a 'good algorithm' in the sense of J. Edmonds. That is, the number of pivots or iterations that may be required is not majorized by any polynomial function of the two parameters that specify the size of the program. (Author)

Cited by 752 works.

Authors

References