Online Spanners in Metric Spaces
Online Spanners in Metric Spaces
复制标题
DOI：
10.4230/lipics.esa.2022.18
复制
发表时间：
2022-02
期刊：
影响因子：
--
通讯作者：
S. Bhore;Arnold Filtser;Hadi Khodabandeh;Csaba D. T'oth
中科院分区：
文献类型：
--
作者：
S. Bhore;Arnold Filtser;Hadi Khodabandeh;Csaba D. T'oth
给定一个度量空间$\mathcal{M}=（X，\delta）$，$X$上的加权图$G$是$\mathcal{M}$的度量$t$-n，如果对X$中的每一个$u，v，$\delta（u，v）\le d_G（u，v）\le t\cdot \delta（u，v）$，其中$d_G$是$G$中的最短路度量。本文构造了度量空间中有限集的在线空间。在这里，我们给出了一个点序列$（s_1，\ldots，s_n）$，其中点一次一个地呈现（即，在$i$步之后，我们看到$S_i = \{s_1，\ldots，s_i\}$）。当新点到达时，该算法允许向扳手添加边，但是，不允许从扳手中删除任何边。我们的目标是保持$t$-$G_i$为$S_i$的所有$i$，同时最小化边的数量，以及它们的总重量。我们在欧氏$d$-空间中构造了在线$（1+\varepalent）$-空间，在一般度量中构造了$（2k-1）（1+\varepalent）$-空间，在超度量中构造了$（2+\varepalent）$-空间.最值得注意的是，在欧几里德平面上，我们构造了一个竞争比为O（\varepaly ^{-3/2}\log\varepaly ^{-1}\log n）$的$（1+\varepaly）$-xos，绕过了经典的亮度下限$\Omega（\varepaly ^{-2}）$，将xos的重量与MST的重量进行比较。
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.