a tight bound on approximating arbitrary metrics by tree metrics
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.
approximation metrics tree metrics tree paper point metric spaces embeddings distributed log online algorithm group label network design task systems performance