Exponential lower bounds for history-based simplex pivot rules on abstract cubes
Open access
Autor(in)
Datum
2017Typ
- Conference Paper
Abstract
The behavior of the simplex algorithm is a widely studied subject. Specifically, the question of the existence of a polynomial pivot rule for the simplex algorithm is of major importance. Here, we give exponential lower bounds for three history-based pivot rules. Those rules decide their next step based on memory of the past steps. In particular, we study Zadeh's least entered rule, Johnson's least-recently basic rule and Cunningham's least-recently considered (or round-robin) rule. We give exponential lower bounds on Acyclic Unique Sink Orientations of the abstract cube, for all of these pivot rules. For Johnson's rule our bound is the first superpolynomial one in any context; for Zadeh's it is the first one for AUSO. Those two are our main results. Mehr anzeigen
Persistenter Link
https://doi.org/10.3929/ethz-b-000197706Publikationsstatus
publishedExterne Links
Buchtitel
25th Annual European Symposium on Algorithms (ESA 2017)Zeitschrift / Serie
Leibniz International Proceedings in Informatics (LIPIcs)Band
Seiten / Artikelnummer
Verlag
Schloss Dagstuhl - Leibniz-Zentrum für InformatikKonferenz
Thema
pivot rule; lower bound; exponential; unique sink orientation; zadehOrganisationseinheit
03457 - Welzl, Emo (emeritus) / Welzl, Emo (emeritus)