论文标题
在线跨度在公制空间中
Online Spanners in Metric Spaces
论文作者
论文摘要
给定一个度量空间$ \ MATHCAL {m} =（x，δ）$，加权图$ g $ the $ x $是$ \ Mathcal {m} $的公制$ t $ - spanner，如果每个$ u，v \ in x $，$ uny v \ in x $，$Δ（$δ（u，v） $ g $中的最短路径度量。在本文中，我们在在线环境中的度量空间中为有限套装构建了跨度。在这里，我们得到了一系列点$（s_1，\ ldots，s_n）$的顺序，其中一次是一个点（即，在$ i $ step之后，我们看到$ s_i = \ {s_1，\ ldots，s_i \} $）。当新点到达时，允许算法将边缘添加到扳手，但是，不允许从扳手删除任何边缘。目的是为所有$ i $ $ s_i $保持$ t $ spanner $ g_i $，同时最小化边缘数量及其总重量。 我们在线构建$（1+ \ varepsilon）$ - euclidean $ d $ -space，$（2k-1）（1+ \ varepsilon）$ - 通用指标的跨度和$（2+ \ varepsilon）$ - 超X型的跨度。最值得注意的是，在欧几里得飞机上，我们构建了一个$（1+ \ varepsilon）$ - 具有竞争比$ o（\ varepsilon^{ - 3/2} \ log \ log \ varepsilon^{ - 1} { - 1} \ log n）$的竞争比（\ varepsilon^{ - 扳手，到MST。
Given a metric space $\mathcal{M}=(X,δ)$, a weighted graph $G$ over $X$ is a metric $t$-spanner of $\mathcal{M}$ if for every $u,v \in X$, $δ(u,v)\le d_G(u,v)\le t\cdot δ(u,v)$, where $d_G$ is the shortest path metric in $G$. In this paper, we construct spanners for finite sets in metric spaces in the online setting. Here, we are given a sequence of points $(s_1, \ldots, s_n)$, where the points are presented one at a time (i.e., after $i$ steps, we saw $S_i = \{s_1, \ldots , s_i\}$). The algorithm is allowed to add edges to the spanner when a new point arrives, however, it is not allowed to remove any edge from the spanner. The goal is to maintain a $t$-spanner $G_i$ for $S_i$ for all $i$, while minimizing the number of edges, and their total weight. We construct online $(1+\varepsilon)$-spanners in Euclidean $d$-space, $(2k-1)(1+\varepsilon)$-spanners for general metrics, and $(2+\varepsilon)$-spanners for ultrametrics. Most notably, in Euclidean plane, we construct a $(1+\varepsilon)$-spanner with competitive ratio $O(\varepsilon^{-3/2}\log\varepsilon^{-1}\log n)$, bypassing the classic lower bound $Ω(\varepsilon^{-2})$ for lightness, which compares the weight of the spanner, to that of the MST.
