Greedy spanners are optimal in doubling metrics
Greedy spanners are optimal in doubling metrics
复制标题
贪婪扳手在加倍指标方面是最佳的
DOI：
10.1137/1.9781611975482.145
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Christian Wulff
中科院分区：
文献类型：
--
作者：
G. Borradaile;Hung Le;Christian Wulff
我们证明了贪婪算法构造了一个$（1+\mathrm）$-矩阵的权重为$\mathrm ^{-O（d）}w（\mathrm{MST}）$的点集的度量的两倍$d$，解决了Gottlieb提出的一个公开问题。我们的结果推广了Narasimhan和Smid的结果，他们证明了d维欧氏空间中的一个点集有一个$（1+\n）$-权最多为$\n ^{-O（d）}w（\mathrm{MST}）$。我们的证明只使用了双重度量的包装性质，从而意味着在欧几里得空间中对相同结果的证明要简单得多。
We show that the greedy spanner algorithm constructs a $(1+\epsilon)$-spanner of weight $\epsilon^{-O(d)}w(\mathrm{MST})$ for a point set in metrics of doubling dimension $d$, resolving an open problem posed by Gottlieb. Our result generalizes the result by Narasimhan and Smid who showed that a point set in $d$-dimension Euclidean space has a $(1+\epsilon)$-spanner of weight at most $\epsilon^{-O(d)}w(\mathrm{MST})$. Our proof only uses the packing property of doubling metrics and thus implies a much simpler proof for the same result in Euclidean space.