The simplex algorithm with the pivot rule of maximizing criterion improvement

✍ Scribed by R.G. Jeroslow

• Publisher: Elsevier Science
• Year: 1973
• Tongue: English
• Weight: 998 KB
• Volume: 4
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(73)90171-4

✦ Synopsis

We extend ;l result of Klee anC Minty by showing that the Simplex Alp,orithm with the pivot rule of maximizing criterion ixrip;ovement is not a good algorithm in the sense of Edmonas. The method of proof extends to other similar pivot rules. * Original version rlzceived 7 July 3.97 1.

* As Klee and Minty note in 161, Gale (How to solve linear inequalities, Am. Matil. Monthly 76 (1969) 589-591'9:; hai regarded the determination of the ccmputational complexity of linear programming as a task which "has stood as a challenge to $orkers in the field for twenty years now and remains, irk my opinion, the principal ope.1 question in the ?heory of linear computation."