
Accession Number : AD0706119
Title : HOW GOOD IS THE SIMPLEX ALGORITHM,
Descriptive Note : Technical rept.,
Corporate Author : WASHINGTON UNIV SEATTLE DEPT OF MATHEMATICS
Personal Author(s) : Klee,Victor ; Minty,George J.
Report Date : FEB 1970
Pagination or Media Count : 30
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)
Descriptors : (*SIMPLEX METHOD, EFFICIENCY), LINEAR PROGRAMMING, ALGORITHMS, ITERATIONS, INEQUALITIES, THEOREMS
Subject Categories : Operations Research
Distribution Statement : APPROVED FOR PUBLIC RELEASE