The power of deferral: maintaining a constant-competitive steiner tree online
The power of deferral: maintaining a constant-competitive steiner tree online
复制标题
延期的力量：在线维持持续竞争的斯坦纳树
DOI：
10.1145/2488608.2488674
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Amit Kumar
中科院分区：
文献类型：
--
作者：
Albert Gu;Anupam Gupta;Amit Kumar
在在线施泰纳树问题中，一系列点揭示了一个点：当点到达时，我们只有时间添加单个边缘，将此点连接到先前的点，我们想最大程度地减少总长度添加了边缘。在这里，二十年来已经知道了一个紧密的界限：贪婪的算法维护着一棵树，其成本为o（log n）乘以坦纳树的成本，这是最好的。但是，假设，除了添加的新边缘外，我们还有时间从以前的边缘更改单个边缘：我们可以做得更好吗？例如，我们可以维护持续竞争力的树吗？
我们肯定地回答了这个问题。我们给出了一种原始的偶算算法，该算法仅对每个步骤进行一次互换（除了添加将新点连接到上一点的边缘之外），因此，树的成本仅是最佳成本的恒定时间。我们的双重分析与以前仅原始分析完全不同。特别是，我们在双球半径和树边缘的长度之间给予对应关系。由于双球与点相关，因此不会四处移动（与边缘相比），我们可以根据双半径密切监视边缘长度。表明这些双半径不能太快改变是纸张的技术心脏，并且允许我们在始终保持恒定竞争树的同时对每次到达的互换数量进行艰难界定。此问题的先前结果给出了一种执行摊销恒定掉期数量的算法：对于每个n，第一个$ n $ steps中的互换数为o（n）。我们还为这种摊销情况提供了更简单的严格分析。
In the online Steiner tree problem, a sequence of points is revealed one-by-one: when a point arrives, we only have time to add a single edge connecting this point to the previous ones, and we want to minimize the total length of edges added. Here, a tight bound has been known for two decades: the greedy algorithm maintains a tree whose cost is O(log n) times the Steiner tree cost, and this is best possible. But suppose, in addition to the new edge we add, we have time to change a single edge from the previous set of edges: can we do much better? Can we, e.g., maintain a tree that is constant-competitive?
We answer this question in the affirmative. We give a primal-dual algorithm that makes only a single swap per step (in addition to adding the edge connecting the new point to the previous ones), and such that the tree's cost is only a constant times the optimal cost. Our dual-based analysis is quite different from previous primal-only analyses. In particular, we give a correspondence between radii of dual balls and lengths of tree edges; since dual balls are associated with points and hence do not move around (in contrast to edges), we can closely monitor the edge lengths based on the dual radii. Showing that these dual radii cannot change too rapidly is the technical heart of the paper, and allows us to give a hard bound on the number of swaps per arrival, while maintaining a constant-competitive tree at all times. Previous results for this problem gave an algorithm that performed an amortized constant number of swaps: for each n, the number of swaps in the first $n$ steps was O(n). We also give a simpler tight analysis for this amortized case.
在线 MST 和 TSP 的追索权
DOI：
10.1137/130917703
发表时间：
--
期刊：
SIAM J. Comput.
影响因子：
--
作者：
N. Megow;M. Skutella;J. Verschae;A. Wiese.
通讯作者：
A. Wiese.