Abstract: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 ...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)Read More
Publication Year: 1970
Publication Date: 1970-02-01
Language: en
Type: article
Access and Citation
Cited By Count: 811
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot