Approximation algorithms for embedding general metrics into trees

ABSTRACT

We consider the problem of embedding general metrics into trees. We give the first non-trivial approximation algorithm for minimizing the multiplicative distortion. Our algorithm produces an embedding with distortion (c log n)^{O(√log Δ)}, where c is the optimal distortion, and Δ is the spread of the metric (i.e. the ratio of the diameter over the minimum distance). We give an improved O(1)-approximation algorithm for the case where the input is the shortest path metric over an unweighted graph. Moreover, we show that by composing our approximation algorithm for embedding general metrics into trees, with the approximation algorithm of [BCIS05] for embedding trees into the line, we obtain an improved approximation algorithm for embedding general metrics into the line.

We also provide almost tight bounds for the relation between embedding into trees and embedding into spanning subtrees. We show that for any unweighted graph G, the ratio of the distortion required to embed G into a spanning subtree, over the distortion of an optimal tree embedding of G, is at most O(log n). We complement this bound by exhibiting a family of graphs for which the ratio is Ω(log n/log log n).

REFERENCES

• 1: Noga Alon , Mihai Bădoiu , Erik D. Demaine , Martin Farach-Colton , MohammadTaghi Hajiaghayi , Anastasios Sidiropoulos, Ordinal embeddings of minimum relaxation: general properties, trees, and ultrametrics, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 2: Richa Agarwala , Vineet Bafna , Martin Farach , Babu Narayanan , Mike Paterson , Mikkel Thorup, On the approximability of numerical taxonomy (fitting distances by tree metrics), Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.365-372, January 28-30, 1996, Atlanta, Georgia, United States
• 3: Nir Ailon , Moses Charikar, Fitting tree metrics: Hierarchical clustering and Phylogeny, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.73-82, October 23-25, 2005 [doi>10.1109/SFCS.2005.36]
• 4: Mihai Bǎdoiu , Julia Chuzhoy , Piotr Indyk , Anastasios Sidiropoulos, Low-distortion embeddings of general metrics into the line, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060624]
• 5: Mihai Bǎdoiu , Julia Chuzhoy , Piotr Indyk , Anastasios Sidiropou, Embedding ultrametrics into low-dimensional spaces, Proceedings of the twenty-second annual symposium on Computational geometry, June 05-07, 2006, Sedona, Arizona, USA [doi>10.1145/1137856.1137886]
• 6: Mihai Bǎdoiu , Kedar Dhamdhere , Anupam Gupta , Yuri Rabinovich , Harald Räcke , R. Ravi , Anastasios Sidiropoulos, Approximation algorithms for low-distortion embeddings into low-dimensional spaces, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 7: Leizhen Cai , Derek G. Corneil, Tree Spanners, SIAM Journal on Discrete Mathematics, v.8 n.3, p.359-387, Aug. 1995 [doi>10.1137/S0895480192237403]
• 8: {DEKM98} R. Durbin, S. Eddy, A. Krogh, and G. Mitchison. Biological sequence analysis. Cambridge University Press, 1998.
• 9: Yuval Emek , David Peleg, Approximating Minimum Max-Stretch spanning Trees on unweighted graphs, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 10: {Epp00} D. Eppstein. Spanning trees and spanners. Handbook of Computational Geometry (Ed. J.-R. Sack and J. Urrutia), pages 425--461, 2000.
• 11: Martin Farach , Sampath Kannan , Tandy Warnow, A robust model for finding optimal evolutionary trees, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.137-145, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167132]
• 12: Sándor P. Fekete , Jana Kremer, Tree spanners in planar graphs, Discrete Applied Mathematics, v.108 n.1, p.85-103, Feb. 15,2001 [doi>10.1016/S0166-218X(00)00226-2]
• 13: Anupam Gupta, Steiner points in tree metrics don't (really) help, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.220-227, January 07-09, 2001, Washington, D.C., United States
• 14: {HKM05} Boulos Harb, Sampath Kannan, and Andrew McGregor. Approximating the best-fit tree under lp norms. In Proceedings of Approx, 2005.
• 15: {HP05} Alexander Hall and Christos H. Papadimitriou. Approximating the distortion. In APPROX-RANDOM, pages 111--122, 2005.
• 16: 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
• 17: Claire Kenyon , Yuval Rabani , Alistair Sinclair, Low distortion maps between point sets, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007398]
• 18: {KTT98} A. Kearsley, R. Tapia, and M. Trosset. The solution of the metric stress and sstress problems in multidimensional scaling using newtons method. Computational Statistics, 1998.
• 19: {Lin02} N. Linial. Finite metric spaces - combinatorics, geometry and algorithms. Proc. International Congress of Mathematicians III, pages 573--586, 2002.
• 20: {LLR94} N. Linial, E. London, and Y. Rabinovich. The geometry of graphs and some of its algorithmic applications. Proc. 35th Annual IEEE Symposium on Foundations of Computer Science, pages 577--591, 1994.
• 21: James R. Lee , Assaf Naor , Yuval Peres, Trees and Markov convexity, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.1028-1037, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109671]
• 22: {Mat90} J. Matoušek. Bi-lipschitz embeddings into lowdimensional euclidean spaces. Comment. Math. Univ. Carolinae, 31:589--600, 1990.
• 23: {MDS} MDS: Working Group on Algorithms for Multidimensional Scaling. Algorithms for multidimensional scaling. DIMACS Web Page.
• 24: David Peleg , Eilon Reshef, A Variant of the Arrow Distributed Directory with Low Average Complexity, Proceedings of the 26th International Colloquium on Automata, Languages and Programming, p.615-624, July 11-15, 1999
• 25: Christos Papadimitriou , Shmuel Safra, The complexity of low-distortion embeddings between point sets, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 26: D. Peleg , D. Tendler, Low Stretch Spanning Trees for Planar Graphs,, Weizmann Science Press of Israel, Jerusalem, Israel, 2001
• 27: David Peleg , Jeffrey D. Ullman, An optimal synchronizer for the hypercube, Proceedings of the sixth annual ACM Symposium on Principles of distributed computing, p.77-85, August 10-12, 1987, Vancouver, British Columbia, Canada [doi>10.1145/41840.41847]
• 28: {Sci05} Will there ever be a tree of life that systematists can agree on? Science, 125th Anniversary Issue. Available at http://www.sciencemag.org/sciext/125th/, 2005.
• 29: G. Venkatesan , U. Rotics , M. S. Madanlal , J. A. Makowsky , C. Pandu Rangan, Restrictions of minimum spanner problems, Information and Computation, v.136 n.2, p.143-164, Aug. 1, 1997 [doi>10.1006/inco.1997.2641]