The Power of Recourse for Online MST and TSP
The Power of Recourse for Online MST and TSP
复制标题
在线 MST 和 TSP 的追索权
DOI：
10.1137/130917703
复制
发表时间：
--
期刊：
影响因子：
--
通讯作者：
A. Wiese.
中科院分区：
文献类型：
--
作者：
N. Megow;M. Skutella;J. Verschae;A. Wiese.
我们考虑在线版本的最小生成树（MST）问题和旅行商问题（TSP），其中追索权是允许的。具有度量边代价的未知图的节点一个接一个地出现，并且必须以这样一种方式连接，从而使生成的树或游具有低代价。在标准在线环境下，由于决策不可撤销，没有任何算法可以保证竞争比不变。在我们的模型中，我们通过给予每次迭代的边缘重排的有限预算来允许追索权行动。一个带有常数（平摊）预算的在线算法能否保证常近似解是一个20多年来悬而未决的问题。作为我们的主要结果，我们在平摊情况下肯定地回答了这个问题。我们介绍了一种算法，当给定一个常数的平摊预算时，它保持一个接近最优树。与经典的TSP变体不同，标准的双树和捷径方法不能在在线设置中提供恒定的保证。我们提出了一种非平凡的鲁棒捷径技术，允许在损失小因素的情况下将在线MST结果转换为TSP结果。
We consider online versions of the minimum spanning tree (MST) problem and the traveling salesman problem (TSP) where recourse is allowed. The nodes of an unknown graph with metric edge cost appear one by one and must be connected in such a way that the resulting tree or tour has low cost. In the standard online setting, with irrevocable decisions, no algorithm can guarantee a constant-competitive ratio. In our model we allow recourse actions by giving a limited budget of edge rearrangements per iteration. It has been an open question for more than 20 years whether an online algorithm equipped with a constant (amortized) budget can guarantee constant-approximate solutions. As our main result, we answer this question affirmatively in an amortized setting. We introduce an algorithm that maintains a nearly optimal tree when given a constant amortized budget. Unlike in classical TSP variants, the standard double-tree and shortcutting approach does not give constant guarantees in the online setting. We propose a nontrivial robust shortcutting technique that allows translation of online MST results into TSP results at the loss of small factors.
登录
查看更多内容
并非所有插入方法都会在欧几里得平面上产生恒定的近似游览
DOI：
10.1016/0304-3975(94)90257-7
发表时间：
1994
期刊：
Theor. Comput. Sci.
影响因子：
--
作者：
V. Bafna;B. Kalyanasundaram;K. Pruhs
通讯作者：
K. Pruhs
带有删除的在线斯坦纳树
DOI：
10.1137/1.9781611973402.34
发表时间：
2013
期刊：
ArXiv
影响因子：
--
作者：
Anupam Gupta;Amit Kumar
通讯作者：
Amit Kumar
Steiner 树问题的在线算法（扩展摘要）
DOI：
--
发表时间：
1997
期刊：
Symposium on the Theory of Computing
影响因子：
--
作者：
P. Berman;C. Coulston
通讯作者：
C. Coulston
延期的力量：在线维持持续竞争的斯坦纳树
DOI：
10.1145/2488608.2488674
发表时间：
2013
期刊：
ArXiv
影响因子：
--
作者：
Albert Gu;Anupam Gupta;Amit Kumar
通讯作者：
Amit Kumar
欧几里得平面上的在线斯坦纳树
DOI：
--
发表时间：
1992
期刊：
SCG '92
影响因子：
--
作者：
N. Alon;Y. Azar
通讯作者：
Y. Azar