Given a metric space $\mathcal{M}=(X,\delta)$, a weighted graph $G$ over $X$ is a metric $t$-spanner of $\mathcal{M}$ if for every $u,v \in X$, $\delta(u,v)\le d_G(u,v)\le t\cdot \delta(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 $\Omega(\varepsilon^{-2})$ for lightness, which compares the weight of the spanner, to that of the MST.
翻译:(d) d_G$是G$中最短的路径。在本文中,我们为在线设置的内位设置了一定的平方美元。在这里,我们得到了一个分数序列 $(1,\1,\xxx美元,$delta(u,v)\led d_G(u,v)\le t\delta(x,v)$), d_G$是美元中最短的路径。当新点到达时,我们无法从在线设置的内位中去除任何边缘。