An exponential lower bound for Zadeh’s pivot rule
An exponential lower bound for Zadeh’s pivot rule
复制标题
Zadeh 枢轴规则的指数下界
DOI：
--
复制
发表时间：
2019
影响因子：
2.7
通讯作者：
Alexander V. Hopp
中科院分区：
文献类型：
--
作者：
Y. Disser;Oliver Friedmann;Alexander V. Hopp
单纯形算法是否存在有效的主元规则是离散优化中最重要的问题之一。虽然许多自然的、确定性的主元规则都可以产生指数级的运行时间，但随机面规则的运行时间是次指数级的。在很长一段时间里，扎德规则仍然是第一个具有次指数运行时间的确定性主元规则的最突出的候选者。我们提出了一个下界的建设，表明扎德的规则实际上是指数在最坏的情况下。我们的建设是基于一个密切的关系，奇偶博弈的策略改进算法和马尔可夫决策过程的政策迭代算法，我们也获得指数下界扎德规则在这些情况下。
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.
登录
查看更多内容
DOI：
10.1007/978-3-642-20807-2_16
发表时间：
2011-06
期刊：
--
影响因子：
--
作者：
Oliver Friedmann
通讯作者：
Oliver Friedmann
最新确定性策略迭代算法的指数下界
DOI：
10.2168/lmcs-7(3:23)2011
发表时间：
2011
期刊：
Log. Methods Comput. Sci.
影响因子：
--
作者：
Oliver Friedmann
通讯作者：
Oliver Friedmann
影响因子：
2.7
作者：
David Avis;Oliver Friedmann
通讯作者：
Oliver Friedmann
单纯形算法具有 NP 强大性
DOI：
10.1145/3280847
发表时间：
2018
期刊：
ACM Transactions on Algorithms (TALG)
影响因子：
--
作者：
Disser;Skutella;Martin
通讯作者：
Martin
关于扎德枢轴规则的弗里德曼次指数下界
DOI：
10.1007/978-3-030-17953-3_13
发表时间：
2019
期刊：
影响因子：
--
作者：
Disser;A.V. Lodi;Nagarajan;V. (eds.)
通讯作者：
V. (eds.)