TU Darmstadt / ULB / TUbiblio

An Exponential Lower Bound for Zadeh's pivot rule

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 Frage zum Eintrag

Optionen (nur für Redakteure)
Redaktionelle Details anzeigen Redaktionelle Details anzeigen