A tight bound on approximating arbitrary metrics by tree metrics

详细信息	查看全文 | 推荐本文 |

• 作者：Fakcharoenphol ; Jittat ; Rao ; Satish ; Talwar ; Kunal
• 关键词：Metrics ; Embeddings ; Tree Metrics
• 刊名：Journal of Computer and System Sciences
• 出版年：2004
• 期刊代码：186_00220000
• 类别：et
• 出版时间：November, 2004
• 卷：69
• 期：3
• 页码：485-497
• 文件大小：319 K

摘要

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(logn). This improves upon the result of Bartal who gave a bound of O(lognloglogn). Moreover, our result is existentially tight; there exist metric spaces where any tree embedding must have distortion Ω(logn)-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.