Improved embeddings of graph metrics into random trees

ABSTRACT

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² 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³ 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² 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.

REFERENCES

• 1: Noga Alon , Richard M. Karp , David Peleg , Douglas West, A Graph-Theoretic Game and its Application to the $k$-Server Problem, SIAM Journal on Computing, v.24 n.1, p.78-100, Feb. 1995 [doi>10.1137/S0097539792224474]
• 2: B. Awerbuch , Y. Azar, Buy-at-bulk network design, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.542, October 19-22, 1997
• 3: Y. Bartal, Probabilistic approximation of metric spaces and its algorithmic applications, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.184, October 14-16, 1996
• 4: Yair Bartal, On approximating arbitrary metrices by tree metrics, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.161-168, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276725]
• 5: Gruia Calinescu , Howard Karloff , Yuval Rabani, Approximation algorithms for the 0-extension problem, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.8-16, January 07-09, 2001, Washington, D.C., United States
• 6: Moses Charikar , Chandra Chekuri , Ashish Goel , Sudipto Guha, Rounding via trees: deterministic approximation algorithms for group Steiner trees and k-median, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.114-123, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276719]
• 7: Moses Charikar , Chandra Chekuri , Ashish Goel , Sudipto Guha , Serge Plotkin, Approximating a Finite Metric by a Small Number of Tree Metrics, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.379, November 08-11, 1998
• 8: Chandra Chekuri , Anupam Gupta , Ilan Newman , Yuri Rabinovich , Alistair Sinclair, Embedding k-outerplanar graphs into ℓ1, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 9: Michael Elkin , Yuval Emek , Daniel A. Spielman , Shang-Hua Teng, Lower-stretch spanning trees, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060665]
• 10: Jittat Fakcharoenphol , Satish Rao , Kunal Talwar, A tight bound on approximating arbitrary metrics by tree metrics, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780608]
• 11: Naveen Garg , Goran Konjevod , R. Ravi, A polylogarithmic approximation algorithm for the Steiner group tree problem, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.253-259, January 25-27, 1998, San Francisco, California, United States
• 12: Anupam Gupta , Ilan Newman , Yuri Rabinovich , Alistair Sinclair, Cuts, Trees and ℓ₁-Embeddings of Graphs*, Combinatorica, v.24 n.2, p.233-269, April 2004 [doi>10.1007/s00493-004-0015-x]
• 13: P. Indyk, Algorithmic Applications of Low-Distortion Geometric Embeddings, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.10, October 14-17, 2001
• 14: Jon Kleinberg , Éva Tardos, Approximation algorithms for classification problems with pairwise relationships: metric labeling and Markov random fields, Journal of the ACM (JACM), v.49 n.5, p.616-639, September 2002 [doi>10.1145/585265.585268]
• 15: P. D. Seymour, Packing directed circuits fractionally, Combinatorica, 15 (1993), pp. 182--188.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Probabilistic computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees

General Terms:
Algorithms, Theory