Approximation algorithms for low-distortion embeddings into low-dimensional spaces

ABSTRACT

We present several approximation algorithms for the problem of embedding metric spaces into a line, and into the two-dimensional plane. Among other results, we give an O(√n)-approximation algorithm for the problem of finding a line embedding of a metric induced by a given unweighted graph, that minimizes the (standard) multiplicative distortion. We give an improved Õ(n^1/3) approximation for the case of metrics generated by unweighted trees. This is the first result of this type.

REFERENCES

• 1: 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
• 2: {BIR03} M. Badoiu, P. Indyk, and Y. Rabinovich. Approximate algorithms for embedding metrics into low-dimensional spaces. Manuscript, 2003.
• 3: {BJDG+03} Z. Bar-Joseph, E. D. Demaine, D. K. Gifford, A. M. Hamel, Tommi S. Jaakkola, and Nathan Srebro. K-ary clustering with optimal leaf ordering for gene expression data. Bioinformatics, 19(9):1070--8, 2003.
• 4: {Bor33} K. Borsuk. Drei Sätze über die n-dimensionale euklidische Sphäre. Fund. Math., 20:177--190, 1933.
• 5: {Bou85} J. Bourgain. On lipschitz embedding of finite metric spaces into hilbert space. Isreal Journal of Mathematics, 52:46--52, 1985.
• 6: Mihai Bâdoiu, Approximation algorithm for embedding metrics into a two-dimensional space, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 7: {Dha04} Kedar Dhamdhere. Approximating additive distortion of embeddings into line metrics. 7th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), 2004.
• 8: 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]
• 9: Uriel Feige, Approximating the bandwidth via volume respecting embeddings, Journal of Computer and System Sciences, v.60 n.3, p.510-539, June 2000 [doi>10.1006/jcss.1999.1682]
• 10: Anupam Gupta, Improved bandwidth approximation for trees, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.788-793, January 09-11, 2000, San Francisco, California, United States
• 11: Johan Håstad , Lars Ivansson , Jens Lagergren, Fitting Points on the Real Line and Its Application to RH Mapping, Proceedings of the 6th Annual European Symposium on Algorithms, p.465-476, August 24-26, 1998
• 12: 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
• 13: {Iva00} L. Ivansson. Computational aspects of radiation hybrid. Doctoral Dissertation, Department of Numerical Analysis and Computer Science, Royal Institute of Technology, 2000.
• 14: {Kir34} M. D. Kirszbraun. Über die zusammenziehenden und lipschitzschen Transformationen. Fund. Math., 22:77--108, 1934.
• 15: 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]
• 16: {Kru64a} J. B. Kruskal. Multidimensional scaling by optimizing goodness of fit to a nonmetric hypothesis. Psychometrika, 29:1--27, 1964.
• 17: {Kru64b} J. B. Kruskal. Nonmetric multidimensional scaling: A numerical method. Psychometrika, 29:115--129, 1964.
• 18: {LLR94} N. Linial, E. London, and Y. Rabinovich. The geometry of graphs and some of its algorithmic applications. Proceedings of 35th Annual IEEE Symposium on Foundations of Computer Science, pages 577--591, 1994.
• 19: {LN} J. R. Lee and A. Naor. Absolute lipschitz extendability. Comptes Rendus de l'Académie des Sciences - Series 1 - Mathematics. to appear.
• 20: {Mat90} J. Matoušek, Bi-lipschitz embeddings into low-dimensional euclidean spaces. Comment. Math. Univ. Carolinae, 31:589--600, 1990.
• 21: {Mat96} J. Matoušek. On the distortion required for embedding finite metric spaces into normed spaces. Israel Journal of Mathematics, 93:333--344, 1996.
• 22: {Sax80} J. B. Saxe. Dynamic-programming algorithms for recognizing small-bandwidth graphs in polynomial time. SIAM J. Algebraic Discrete Methods, 1:363--369, 1980.
• 23: {She62a} R. N. Shepard. The analysis of proximities: Multi-dimensional scaling with an unknown distance function 1. Psychometrika, 27:125--140, 1962.
• 24: {She62b} R. N. Shepard. The analysis of proximities: Multi-dimensional scaling with an unknown distance function 2. Psychometrika, 27:216--246, 1962.
• 25: {Wor} Working Group on Algorithms for Multidimensional Scaling. Algorithms for multidimensional scaling. http://dimacs.rutgers.edu/Workshops/Algorithms/.