Online Steiner Tree with Deletions
Online Steiner Tree with Deletions
复制标题
带有删除的在线斯坦纳树
DOI：
10.1137/1.9781611973402.34
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Amit Kumar
中科院分区：
文献类型：
--
作者：
Anupam Gupta;Amit Kumar
在在线施泰纳树问题中，输入是一组出现的顶点，我们必须在当前的顶点上维护施泰纳树。树，我们希望这种成本接近所有时间点的最佳施泰纳树的成本。几十年来。一个新的边缘，并在每个顶点到达时进行一个边缘交换，我们仍然可以在线维护恒定竞争的树。
但是，如果一组顶点再次看到添加和删除，我们想获得一台低成本的施泰纳树，而imase和Waxman的原始纸（3）：369--384，1991）也考虑了该模型，它给出了一种算法，最多可为前N请求进行O（n3/2）边缘更改，并在线维护了恒定的树。在本文中，我们改进了这些结果：
•我们给出了一种在线算法，该算法仅在删除下维护一棵坦源树：我们从一组顶点开始，并且每次从此组中删除其中一个顶点---我们的Steiner树不再需要跨越此vertex 。进行这些恒定数量的更改。
•我们还提供了一种算法，该算法在完全动态模型中维护施泰纳树（每个请求都会添加或删除顶点）。
In the online Steiner tree problem, the input is a set of vertices that appear one-by-one, and we have to maintain a Steiner tree on the current set of vertices. The cost of the tree is the total length of edges in the tree, and we want this cost to be close to the cost of the optimal Steiner tree at all points in time. If we are allowed to only add edges, a tight bound of Θ(log n) on the competitiveness has been known for two decades. Recently it was shown that if we can add one new edge and make one edge swap upon every vertex arrival, we can still maintain a constant-competitive tree online.
But what if the set of vertices sees both additions and deletions? Again, we would like to obtain a low-cost Steiner tree with as few edge changes as possible. The original paper of Imase and Waxman (SIAM J. Disc. Math, 4(3): 369--384, 1991) had also considered this model, and it gave an algorithm that made at most O(n3/2) edge changes for the first n requests, and maintained a constant-competitive tree online. In this paper we improve on these results:
• We give an online algorithm that maintains a Steiner tree under only deletions: we start off with a set of vertices, and at each time one of the vertices is removed from this set---our Steiner tree no longer has to span this vertex. We give an algorithm that changes only a constant number of edges upon each request, and maintains a constant-competitive tree at all times. Our algorithm uses the primal-dual framework and a global charging argument to carefully make these constant number of changes.
• We also give an algorithm that maintains a Steiner tree in the fully-dynamic model (where each request either adds or deletes a vertex). Our algorithm for this setting makes a constant number of changes per request in an amortized sense.
在线 MST 和 TSP 的追索权
DOI：
10.1137/130917703
发表时间：
--
期刊：
SIAM J. Comput.
影响因子：
--
作者：
N. Megow;M. Skutella;J. Verschae;A. Wiese.
通讯作者：
A. Wiese.