Disser, Yann ; Hopp, Alexander V. (2018)
On Friedmann's subexponential lower bound for Zadeh's pivot rule.
Report, Primary publication
This is the latest version of this item.
|
Text
[Disser, Hopp] On Friedmann's subexponential lower bound for Zadeh's pivot rule.pdf Copyright Information: CC BY-ND 4.0 International - Creative Commons, Attribution NoDerivs. Download (519kB) | Preview |
Item Type: | Report |
---|---|
Type of entry: | Primary publication |
Title: | On Friedmann's subexponential lower bound for Zadeh's pivot rule |
Language: | English |
Date: | 5 November 2018 |
Place of Publication: | Darmstadt |
Edition: | 2. revised version |
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. |
URN: | urn:nbn:de:tuda-tuprints-75572 |
Classification DDC: | 500 Science and mathematics > 510 Mathematics |
Divisions: | Exzellenzinitiative > Graduate Schools > Graduate School of Computational Engineering (CE) 04 Department of Mathematics > Optimization > Discrete Optimization |
Date Deposited: | 05 Nov 2018 11:09 |
Last Modified: | 19 Sep 2023 18:01 |
URI: | https://tuprints.ulb.tu-darmstadt.de/id/eprint/7557 |
PPN: | 438501039 |
Export: |
Available Versions of this Item
-
On Friedmann's subexponential lower bound for Zadeh's pivot rule. (deposited 26 Oct 2017 14:00)
- On Friedmann's subexponential lower bound for Zadeh's pivot rule. (deposited 05 Nov 2018 11:09) [Currently Displayed]
View Item |