On-line steiner trees in the Euclidean plane
On-line steiner trees in the Euclidean plane
复制标题
欧几里得平面上的在线斯坦纳树
DOI：
--
复制
发表时间：
1992
期刊：
影响因子：
--
通讯作者：
Y. Azar
中科院分区：
文献类型：
--
作者：
N. Alon;Y. Azar
假设我们在欧氏平面上给定一个n点序列，我们的目标是在线构造一个连接所有这些点的连通图，试图最小化其边的长度总和。这些点一次出现一个，并且在每一步，在线算法必须通过将新点连接到先前构建的图来构建包含所有当前点的连接图。这可以通过将新点（不一定是直线）连接到先前图形的任何点（不一定是给定点之一）来完成。我们的算法的性能是衡量其竞争比：上确界，在所有的点序列，我们的算法构建的图的总长度和最好的Steiner树，连接所有的点的总长度之间的比率。已知的在线算法对所有度量空间的竞争比都是O（logn），但对某些人为的离散度量空间，唯一已知的下界是[IW]。此外，对于飞机，在线算法可以更强大，并实现更好的竞争比，并没有非平凡的最佳可能的竞争比的下限是已知的。在这里，我们证明了一个几乎紧的下界Ω（logn/log logn）的任何在线算法的竞争比。这个下界对确定性算法和随机算法都成立，而且显然对维数大于2的任何欧几里得空间也成立。
Suppose we are given a sequence ofn points in the Euclidean plane, and our objective is to construct, on-line, a connected graph that connects all of them, trying to minimize the total sum of lengths of its edges. The points appear one at a time, and at each step the on-line algorithm must construct a connected graph that contains all current points by connecting the new point to the previously constructed graph. This can be done by joining the new point (not necessarily by a straight line) to any point of the previous graph (not necessarily one of the given points). The performance of our algorithm is measured by its competitive ratio: the supremum, over all sequences of points, of the ratio between the total length of the graph constructed by our algorithm and the total length of the best Steiner tree that connects all the points. There are known on-line algorithms whose competitive ratio isO(logn) even for all metric spaces, but the only lower bound known is of [IW] for some contrived discrete metric space. Moreover, for the plane, on-line algorithms could have been more powerful and achieve a better competitive ratio, and no nontrivial lower bounds for the best possible competitive ratio were known. Here we prove an almost tight lower bound of Ω(logn/log logn) for the competitive ratio of any on-line algorithm. The lower bound holds for deterministic algorithms as well as for randomized ones, and obviously holds in any Euclidean space of dimension greater than 2 as well.