On Friedmann's Subexponential Lower Bound for Zadeh's Pivot Rule
On Friedmann's Subexponential Lower Bound for Zadeh's Pivot Rule
复制标题
关于扎德枢轴规则的弗里德曼次指数下界
DOI：
10.1007/978-3-030-17953-3_13
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
V. (eds.)
中科院分区：
文献类型：
--
作者：
Disser;A.V. Lodi;Nagarajan;V. (eds.)
单纯形法是否接受多项式时间轴规则的问题一直是离散优化中最重要的开放问题之一。在Friedmann(IPCO，2011)基于与马尔可夫决策过程(MDP)的策略迭代算法的密切关系提出一个次指数实例之前，Zadeh的枢轴规则一直是一个很有前途的候选规则。我们研究了Friedmann的下界结构，发现了他的分析中的三个缺陷：(A)策略迭代的初始策略没有产生所需的发生记录和改进开关，(B)发生记录的规范并不完全准确，以及(C)Friedmann描述的改进开关序列不一致地遵循Zadeh的枢轴规则。在本文中，我们将逐一解决这些问题。虽然前两个问题只需要对初始保单和事件记录的规范进行较小的更改，但第三个问题需要更复杂的排序和相关的平局打破规则，这些规则符合Least-Entered Pivot规则。最重要的是，我们的改变不会影响弗里德曼的MDP的宏观结构，因此我们能够保留他原来的结果。
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 construction and exhibit three flaws in his analysis: 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 described by Friedmann does not consistently follow Zadeh’s pivot rule. In this paper, we resolve each of these issues. 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 theLeast-Enteredpivot 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.
登录
查看更多内容
关于布兰德旋转规则的注释
DOI：
--
发表时间：
1978
期刊：
影响因子：
--
作者：
D. Avis;V. Chvátal
通讯作者：
V. Chvátal
DOI：
10.1007/978-3-642-20807-2_16
发表时间：
2011-06
期刊：
--
影响因子：
--
作者：
Oliver Friedmann
通讯作者：
Oliver Friedmann
最陡边单纯形法的最坏情况行为
影响因子：
1.1
作者：
D. Goldfarb;William Y. Sit
通讯作者：
William Y. Sit
独特的接收器方向：复杂性、结构和算法
DOI：
--
发表时间：
2017
期刊：
影响因子：
--
作者：
Antonis Thomas
通讯作者：
Antonis Thomas