Improved embeddings of graph metrics into random trees

Kedar Dhamdhere, Anupam Gupta, Harald Räcke

Research output: Contribution to conferencePaperpeer-review


Over the past decade, numerous algorithms have been developed using the fact that the distances in any n-point metric (V, d) can be approximated to within O(log n) by distributions D over trees on the point set V [3, 10]. However, when the metric (V, d) is the shortest-path metric of an edge weighted graph G = (V, E), a natural requirement is to obtain such a result where the support of the distribution D is only over subtrees of G. For a long time, the best result satisfying this stronger requirement was a exp{ √log n log log n} distortion result of Alon et al. [1]. In a recent breakthrough, Elkin et al. [9] improved the distortion to O(log 2 n log log n). (The best lower bound on the distortion is Ω(log n), say, for the n-vertex grid [1].) In this paper, we give a construction that improves the distortion to O(log n), improving slightly on the EEST construction. The main contribution of this paper is in the analysis: we use an algorithm which is similar to one used by EEST to give a distortion of O(log 3 n), but using a new probabilistic analysis, we eliminate one of the logarithmic factors. The ideas and techniques we use to obtain this logarithmic improvement seem orthogonal to those used earlier in such situations - e.g., Seymour's decomposition scheme [.4, 9] or the cutting procedures of CKR/FRT [5, 10], both which do not seem to give a guarantee of better than O(log 2 n log log n) for this problem. We hope that our ideas (perhaps in conjunction with some of these others) will ultimately lead to an O(log n) distortion embedding, of graph metrics into distributions over their spanning trees.

Original languageEnglish (US)
Number of pages9
StatePublished - 2006
EventSeventeenth Annual ACM-SIAM Symposium on Discrete Algorithms - Miami, FL, United States
Duration: Jan 22 2006Jan 24 2006


OtherSeventeenth Annual ACM-SIAM Symposium on Discrete Algorithms
Country/TerritoryUnited States
CityMiami, FL

ASJC Scopus subject areas

  • Software
  • General Mathematics


Dive into the research topics of 'Improved embeddings of graph metrics into random trees'. Together they form a unique fingerprint.

Cite this