Disser, Y. ; Friedmann, O. ; Hopp, A. V. (2019)
An Exponential Lower Bound for Zadeh's pivot rule.
doi: 10.48550/arXiv.1911.01074
Report, Bibliographie
Kurzbeschreibung (Abstract)
The question whether the Simplex Algorithm admits an efficient pivot rule remains one of the most important open questions in discrete optimization. While many natural, deterministic pivot rules are known to yield exponential running times, the random-facet rule was shown to have a subexponential running time. For a long time, Zadeh's rule remained the most prominent candidate for the first deterministic pivot rule with subexponential running time. We present a lower bound construction that shows that Zadeh's rule is in fact exponential in the worst case. Our construction is based on a close relation to the Strategy Improvement Algorithm for Parity Games and the Policy Iteration Algorithm for Markov Decision Processes, and we also obtain exponential lower bounds for Zadeh's rule in these contexts.
| Typ des Eintrags: | Report |
|---|---|
| Erschienen: | 2019 |
| Autor(en): | Disser, Y. ; Friedmann, O. ; Hopp, A. V. |
| Art des Eintrags: | Bibliographie |
| Titel: | An Exponential Lower Bound for Zadeh's pivot rule |
| Sprache: | Englisch |
| Publikationsjahr: | 4 November 2019 |
| Verlag: | arXiv |
| Reihe: | Optimization and Control |
| Auflage: | 1.Version |
| DOI: | 10.48550/arXiv.1911.01074 |
| URL / URN: | https://arxiv.org/abs/1911.01074v1 |
| Kurzbeschreibung (Abstract): | The question whether the Simplex Algorithm admits an efficient pivot rule remains one of the most important open questions in discrete optimization. While many natural, deterministic pivot rules are known to yield exponential running times, the random-facet rule was shown to have a subexponential running time. For a long time, Zadeh's rule remained the most prominent candidate for the first deterministic pivot rule with subexponential running time. We present a lower bound construction that shows that Zadeh's rule is in fact exponential in the worst case. Our construction is based on a close relation to the Strategy Improvement Algorithm for Parity Games and the Policy Iteration Algorithm for Markov Decision Processes, and we also obtain exponential lower bounds for Zadeh's rule in these contexts. |
| Fachbereich(e)/-gebiet(e): | Exzellenzinitiative Exzellenzinitiative > Graduiertenschulen Exzellenzinitiative > Graduiertenschulen > Graduate School of Computational Engineering (CE) 04 Fachbereich Mathematik 04 Fachbereich Mathematik > Optimierung |
| Hinterlegungsdatum: | 26 Okt 2020 11:31 |
| Letzte Änderung: | 10 Aug 2023 13:56 |
| PPN: | |
| Export: | |
| Suche nach Titel in: | TUfind oder in Google |
 |
Frage zum Eintrag |
Optionen (nur für Redakteure)
 |
Redaktionelle Details anzeigen |
Drucken
Impressum