In this paper, we show that any n point metric space can be embedded into a distribution over dominating tree metrics such that the expected stretch of any edge is O(log n). This improves upon the result of Bartal who gave a bound of O(log n log log n). Moreover, our result is existentially tight; there exist metric spaces where any tree embedding must have distortion Ω(log n)-distortion. This problem lies at the heart of numerous approximation and online algorithms including ones for group Steiner tree, metric labeling, buy-at-bulk network design and metrical task system. Our result improves the performance guarantees for all of these problems.
展开▼
机译:在本文中,我们证明了可以将任何 n I>点度量空间嵌入到主导树度量之上的分布中,从而使任意边的预期延伸为 O(log n) I> 。这改善了Bartal给出 O(log n log log n) I>的界限的结果。而且,我们的结果在本质上是严格的;存在度量空间,其中任何树嵌入都必须具有失真Ω(log n) I>-失真。这个问题是众多近似和在线算法的核心,其中包括用于Steiner组树,度量标签,批量购买网络设计和度量任务系统的算法。我们的结果提高了所有这些问题的性能保证。
展开▼