TU Darmstadt / ULB / TUbiblio

On Friedmann's Subexponential Lower Bound for Zadeh's Pivot Rule

Disser, Y. and Hopp, A.V.
Lodi, A. and Nagarajan, V. (eds.) (2019):
On Friedmann's Subexponential Lower Bound for Zadeh's Pivot Rule.
In: Integer Programming and Combinatorial Optimization, Heidelberg, Springer, pp. 168-180, DOI: 10.1007/978-3-030-17953-3_13,
[Online-Edition: http://tuprints.ulb.tu-darmstadt.de/6873],
[Book Section]

Abstract

The question whether the Simplex method admits a polynomial time pivot rule remains one of the most important open questions in discrete optimization. Zadeh's pivot rule had long been a promising candidate, before Friedmann (IPCO, 2011) presented a subexponential instance, based on a close relation to policy iteration algorithms for Markov decision processes (MDPs). We investigate Friedmann's lower bound example and exhibit three flaws in the corresponding MDP: We show that (a) the initial policy for the policy iteration does not produce the required occurrence records and improving switches, (b) the specification of occurrence records is not entirely accurate, and (c) the sequence of improving switches used by Friedmann does not consistently follow Zadeh's pivot rule. In this paper, we resolve each of these issues by adapting Friedmann's construction. While the first two issues require only minor changes to the specifications of the initial policy and the occurrence records, the third issue requires a significantly more sophisticated ordering and associated tie-breaking rule that are in accordance with the Least-Entered pivot rule. Most importantly, our changes do not affect the macroscopic structure of Friedmann's MDP, and thus we are able to retain his original result.

Item Type: Book Section
Erschienen: 2019
Editors: Lodi, A. and Nagarajan, V.
Creators: Disser, Y. and Hopp, A.V.
Title: On Friedmann's Subexponential Lower Bound for Zadeh's Pivot Rule
Language: English
Abstract:

The question whether the Simplex method admits a polynomial time pivot rule remains one of the most important open questions in discrete optimization. Zadeh's pivot rule had long been a promising candidate, before Friedmann (IPCO, 2011) presented a subexponential instance, based on a close relation to policy iteration algorithms for Markov decision processes (MDPs). We investigate Friedmann's lower bound example and exhibit three flaws in the corresponding MDP: We show that (a) the initial policy for the policy iteration does not produce the required occurrence records and improving switches, (b) the specification of occurrence records is not entirely accurate, and (c) the sequence of improving switches used by Friedmann does not consistently follow Zadeh's pivot rule. In this paper, we resolve each of these issues by adapting Friedmann's construction. While the first two issues require only minor changes to the specifications of the initial policy and the occurrence records, the third issue requires a significantly more sophisticated ordering and associated tie-breaking rule that are in accordance with the Least-Entered pivot rule. Most importantly, our changes do not affect the macroscopic structure of Friedmann's MDP, and thus we are able to retain his original result.

Title of Book: Integer Programming and Combinatorial Optimization
Series Name: LNCS
Volume: 11480
Place of Publication: Heidelberg
Publisher: Springer
ISBN: 978-3-030-17953-3
Divisions: Exzellenzinitiative
Exzellenzinitiative > Graduate Schools
Exzellenzinitiative > Graduate Schools > Graduate School of Computational Engineering (CE)
04 Department of Mathematics
04 Department of Mathematics > Optimization
04 Department of Mathematics > Optimization > Discrete Optimization
Event Title: IPCO 2019
Event Location: Ann Arbor, Michigan, USA
Event Dates: May 22–24, 2019
Date Deposited: 20 Sep 2019 10:35
DOI: 10.1007/978-3-030-17953-3_13
Official URL: http://tuprints.ulb.tu-darmstadt.de/6873
URN: urn:nbn:de:tuda-tuprints-68733
Export:
Suche nach Titel in: TUfind oder in Google

Optionen (nur für Redakteure)

View Item View Item