• search hit 3 of 10
Back to Result List

The Simplex Algorithm in Dimension Three

Please always quote using this URN:urn:nbn:de:0296-matheon-120
  • We investigate the worst-case behavior of the simplex algorithm on linear programs with 3 variables, that is, on 3-dimensional simple polytopes. Among the pivot rules that we consider, the “random edge” rule yields the best asymptotic behavior as well as the most complicated analysis. All other rules turn out to be much easier to study, but also produce worse results: Most of them show essentially worst-possible behavior; this includes both Kalai’s “random-facet” rule, which is known to be subexponential without dimension restriction, as well as Zadeh’s deterministic history-dependent rule, for which no non-polynomial instances in general dimensions have been found so far.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Volker Kaibel, Rafael Mechtel, Micha Shair, Günter M. Ziegler
URN:urn:nbn:de:0296-matheon-120
Referee:Martin Grötschel
Document Type:Preprint, Research Center Matheon
Language:English
Date of first Publication:2004/02/01
Release Date:2003/12/15
Preprint Number:24
Verstanden ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.