Improved embeddings of graph metrics into random trees
Kedar Dhamdhere, Anupam Gupta, Harald Räcke · 2006
Abstract Over the past decade, numerous algorithms have beendeveloped 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 pointset V [3, 9]. However, when the metric (V, d) is theshortest-path metric of an edge weighted graph G = ( V, E), a natural requirement is to obtain such a resultwhere the support of the distribution D is only over subtrees of G. For a long time, the best result satisfyingthis stronger requirement was a exp{plog n log log n}distortion result of Alon et al. [1]. In a recent breakthrough, Elkin et al. [8] improved the distortion to O(log2 n log log n). (The best lower bound on the dis-tortion is \\Omega (log n), say, for the n-vertex grid [1].)In this paper, we give a construction that improves the distortion to O(log2 n), improving slightly on theEEST construction. The main contribution of this paper is in the analysis: we use an algorithm which is simi-lar to one used by EEST to give a distortion of O(log3 n),but using a new probabilistic analysis, we eliminate one of the logarithmic factors. The ideas and techniqueswe use to obtain this logarithmic improvement seem orthogonal to those used earlier in such situations--e.g.,Seymour's decomposition scheme [4, 8] or the cutting procedures of CKR/FRT [5, 9], both which do not seemto give a guarantee of better than O(log2 n log log n) forthis problem. We hope that our ideas (perhaps in conjunction with some of these others) will ultimately leadto an