HOW GOOD IS THE SIMPLEX ALGORITHM,

reportActive / Technical Report | Accession Number: AD0706119 | Need Help?

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

Author(s):
Klee, Victor ; Minty, George J.
Author Organization(s):
WASHINGTON UNIV SEATTLE DEPT OF MATHEMATICS
Descriptive Note:
Technical rept.,
Supplementary Note:
Prepared in cooperation with Boeing Scientific Research Labs., Seattle, Wash. Mathematics Research Lab. Rept. nos. Mathematical Note-643, D1-82-0961.
Pagination:
0030

Security Markings

DOCUMENT & CONTEXTUAL SUMMARY

Distribution:
Approved For Public Release

RECORD

Collection: TR
Identifying Numbers
Report Number(s):
TR-22
Contract/Grant Number(s):
N00014-67-A-0103-0003
Project Number(s):
NR-044-353
 Subject Terms
Communities of Interest:
No COI(s) Identified
Descriptor(s):
(*SIMPLEX METHOD, EFFICIENCY), LINEAR PROGRAMMING, ALGORITHMS, ITERATIONS, INEQUALITIES, THEOREMS
Field(s)/Group(s):
Operations Research
Keyword(s):
PIVOT THEORY
Report Date:
1970 Feb 01