An exponential lower bound for Cunningham’s rule
An exponential lower bound for Cunningham’s rule
复制标题
坎宁安规则的指数下界
DOI：
10.1007/s10107-016-1008-4
复制
发表时间：
2017
影响因子：
2.7
通讯作者：
Oliver Friedmann
中科院分区：
文献类型：
--
作者：
David Avis;Oliver Friedmann
本文给出了应用于奇偶博弈、马尔可夫决策过程和线性规划的Cunningham最少考虑(轮询)规则的一个指数下界。这改进了Friedmann最近在这些问题上对这一规则的次指数界。循环规则确定变量的循环顺序，并从先前选择的变量开始并以给定的循环顺序开始选择下一个枢轴变量。这可能是基于历史的轴心规则类中最简单的例子。我们的结果是基于奇偶对策的一个新的下界构造。由于这种构造的性质，我们还能够得到适用于超立方体的非循环唯一汇方向(Ausos)的轮询规则的指数下界。此外，这些Auso可以实现为多面体。我们相信，对于基于历史的澳大利亚规则来说，这是第一次出现这样的结果，无论是否实现。这篇论文是自成体系的，不需要事先了解平价游戏。
In this paper we give an exponential lower bound for Cunningham’s least recently considered (round-robin) rule as applied to parity games, Markov decision processes and linear programs. This improves a recent subexponential bound of Friedmann for this rule on these problems. The round-robin rule fixes a cyclical order of the variables and chooses the next pivot variable starting from the previously chosen variable and proceeding in the given circular order. It is perhaps the simplest example from the class of history-based pivot rules. Our results are based on a new lower bound construction for parity games. Due to the nature of the construction we are also able to obtain an exponential lower bound for the round-robin rule applied to acyclic unique sink orientations of hypercubes (AUSOs). Furthermore these AUSOs are realizable as polytopes. We believe these are the first such results for history based rules for AUSOs, realizable or not. The paper is self-contained and requires no previous knowledge of parity games.
登录
查看更多内容
马尔可夫决策过程的策略改进算法的复杂性
影响因子：
2.1
作者：
Mary Melekopoglou;A. Condon
通讯作者：
A. Condon
DOI：
10.1109/sfcs.2001.959931
发表时间：
2001-10
期刊：
Proceedings 2001 IEEE International Conference on Cluster Computing
影响因子：
--
作者：
Tibor Szabó;E. Welzl
通讯作者：
Tibor Szabó;E. Welzl
从类型论的证明中提取精确的实际计算程序
DOI：
--
发表时间：
2022
期刊：
影响因子：
--
作者：
Yuya Higashikawa;Naoki Katoh;Junichi Teruyama;Koji Watase;Holger Thies
通讯作者：
Holger Thies
DOI：
10.1007/978-3-642-20807-2_16
发表时间：
2011-06
期刊：
--
影响因子：
--
作者：
Oliver Friedmann
通讯作者：
Oliver Friedmann
DOI：
10.1109/focs.2004.56
发表时间：
2004-10
期刊：
45th Annual IEEE Symposium on Foundations of Computer Science
影响因子：
--
作者：
J. Matoušek;Tibor Szabó
通讯作者：
J. Matoušek;Tibor Szabó