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