Low-distortion embeddings of general metrics into the line

ABSTRACT

A low-distortion embedding between two metric spaces is a mapping which preserves the distances between each pair of points, up to a small factor called distortion. Low-distortion embeddings have recently found numerous applications in computer science.Most of the known embedding results are "absolute",that is, of the form: any metric Y from a given class of metrics C can be embedded into a metric X with low distortion c. This is beneficial if one can guarantee low distortion for all metrics Y in C. However, in any situations, the worst-case distortion is too large to be meaningful. For example, if X is a line metric, then even very simple metrics (an n - point star or an n -point cycle) are embeddable into X only with distortion linear in n. Nevertheless, embeddings into the line (or into low-dimensional spaces) are important for many applications.A solution to this issue is to consider "relative" (or "approximation") embedding problems, where the goal is to design an (a-approxiation) algorithm which, given any metric X from C as an input, finds an embedding of X into Y which has distortion a *cY (X), where cY (X)is the best possible distortion of an embedding of X into Y.In this paper we show algorithms and hardness results for relative embedding problems.In particular we give: •an algorith that, given a general metric M, finds an embedding with distortion O (Δ^3⁄4 poly(c line (M))), where Δ is the spread of M•an algorithm that,given a weighted tree etric M, finds an embedding with distortion poly(c line (M)) •a hardness result, showing that computing minimum line distortion is hard to approximate up to a factor polynomial in n,even for weighted tree metrics with spread Δ=n ^O (1).

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: 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
• 3: Mihai Bǎdoiu , Erik D. Demaine , Mohammad Taghi Hajiaghayi , Piotr Indyk, Low-dimensional embedding with extra information, Proceedings of the twentieth annual symposium on Computational geometry, June 08-11, 2004, Brooklyn, New York, USA [doi>10.1145/997817.997866]
• 4: 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
• 5: M. Bǎdoiu, P. Indyk, and A. Sidiropoulos. A constant-factor approximation algorithm for embedding unweighted graphs into trees. AI Lab Technical Memo AIM-2004-015, 2004.
• 6: K. Dhamdhere. Approximating additive distortion of line embeddings. Proceedings of RANDOM-APPROX, 2004.
• 7: K. Dhamdhere, A. Gupta, and R. Ravi. Approximating average distortion for embeddings into line. Proceedings of the Symposium on Theoretical Aspects of Computer Science (STACS), 2004.
• 8: John Dunagan , Santosh Vempala, On Euclidean Embeddings and Bandwidth Minimization, Proceedings of the 4th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems and 5th International Workshop on Randomization and Approximation Techniques in Computer Science: Approximation, Randomization and Combinatorial Optimization, p.229-240, August 18-20, 2001
• 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: 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]
• 11: 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]
• 12: 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
• 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: 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]
• 15: N. Linial. Finite metric spaces - combinatorics, geometry and algorithms. Proceedings of the International Congress of Mathematicians III, pages 573--586, 2002.
• 16: 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.
• 17: J. Matoušek. Bi-lipschitz embeddings into low-dimensional euclidean spaces. Comment. Math. Univ. Carolinae, 31:589--600, 1990.
• 18: MDS: Working Group on Algorithms for Multidimensional Scaling. Algorithms for multidimensional scaling. DIMACS Web Page.
• 19: 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
• 20: J. B. Tenenbaum, V. de Silva, and J. C. Langford. A global geometric framework for nonlinear dimensionality reduction. http://isomap.stanford.edu/.
• 21: Walter Unger, The Complexity of the Approximation of the Bandwidth Problem, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.82, November 08-11, 1998

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

General Terms:
Algorithms

Keywords:
approxiation algorithms, metric embeddings