A tight bound on approximating arbitrary metrics by tree metrics

  • Jittat Fakcharoenphol ,
  • Satish Rao ,
  • Kunal Talwar

Journal of Computer and System Sciences | , Vol 69(3): pp. 485-497

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 loglog nÞ: Moreover, our result is existentially tight; there exist metric spaces where any tree embedding must have distortion Oð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.