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):

Report Date:

1970-02-01

Pagination or Media Count:

30.0

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

Subject Categories:

  • Operations Research

Distribution Statement:

APPROVED FOR PUBLIC RELEASE