Improved algorithms for optimal embeddings

ABSTRACT

In the last decade, the notion of metric embeddings with small distortion has received wide attention in the literature, with applications in combinatorial optimization, discrete mathematics, and bio-informatics. The notion of embedding is, given two metric spaces on the same number of points, to find a bijection that minimizes maximum Lipschitz and bi-Lipschitz constants. One reason for the popularity of the notion is that algorithms designed for one metric space can be applied to a different one, given an embedding with small distortion. The better distortion, the better the effectiveness of the original algorithm applied to a new metric space.

The goal recently studied by Kenyon et al. [2004] is to consider all possible embeddings between two finite metric spaces and to find the best possible one; that is, consider a single objective function over the space of all possible embeddings that minimizes the distortion. In this article we continue this important direction. In particular, using a theorem of Albert and Atkinson [2005], we are able to provide an algorithm to find the optimal bijection between two line metrics, provided that the optimal distortion is smaller than 13.602. This improves the previous bound of 3 + 2&sqrt;2, solving an open question posed by Kenyon et al. [2004]. Further, we show an inherent limitation of algorithms using the “forbidden pattern” based dynamic programming approach, in that they cannot find optimal mapping if the optimal distortion is more than 7 + 4&sqrt;3 (≃ 13.928). Thus, our results are almost optimal for this method. We also show that previous techniques for general embeddings apply to a (slightly) more general class of metrics.

REFERENCES

• 1: Tatsuya Akutsu , Kyotetsu Kanaya , Akira Ohyama , Asao Fujiyama, Point matching under non-uniform distortions, Discrete Applied Mathematics, v.127 n.1, p.5-21, April 2003 [doi>10.1016/S0166-218X(02)00282-2]
• 2: Albert, M. H., and Atkinson, M. D. 2005. Simple permutations and pattern restricted permutations. Discr. Math. 300, 1-3, 1--15.
• 3: 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]
• 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: S. Belongie , J. Malik , J. Puzicha, Shape Matching and Object Recognition Using Shape Contexts, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.24 n.4, p.509-522, April 2002 [doi>10.1109/34.993558]
• 6: Prosenjit Bose , Jonathan F. Buss , Anna Lubiw, Pattern matching for permutations, Information Processing Letters, v.65 n.5, p.277-283, March 13, 1998 [doi>10.1016/S0020-0190(97)00209-3]
• 7: Bernard Chazelle , Ding Liu , Avner Magen, Sublinear geometric algorithms, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780620]
• 8: Chinn, P., Chvatalova, J., Dewdney, A., and Gibbs, N. 1982. The bandwidth problem for graphs and matrices—A survey. J. Graph Theory 6, 223--254.
• 9: Josep Díaz , Jordi Petit , Maria Serna, A survey of graph layout problems, ACM Computing Surveys (CSUR), v.34 n.3, p.313-356, September 2002 [doi>10.1145/568522.568523]
• 10: Fortin, S. 1996. The graph isomorphism problem. Tech. Rep. 96-20, University of Alberta, Edomonton, Alberta, Canada.
• 11: Hall, A., and Papadimitriou, C. 2005. Approximating the distoriton. In Proceedings of the International Workshop on Randomization and Approximation Techniques (RANDOM APPROX). Lecture Notes in Computer Science, vol. 3624. Springer, 111--122.
• 12: Frank Hoffmann , Klaus Kriegel , Carola Wenk, Matching 2D patterns of protein spots, Proceedings of the fourteenth annual symposium on Computational geometry, p.231-239, June 07-10, 1998, Minneapolis, Minnesota, United States [doi>10.1145/276884.276911]
• 13: Roger A. Horn , Charles R. Johnson, Matrix analysis, Cambridge University Press, New York, NY, 1985
• 14: Johnson, W., and Lindenstrauss, J. 2003. Handbook of Geometry of Banach Spaces. North-Holland.
• 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: Kruskal, J. 1964a. Multidimensional scaling by optimizing goodness of fit to a nonmetric hypothesis. Pyschometrika 29, 1--27.
• 17: Kruskal, J. 1964b. Nonmetric multidimensional scaling: A numerical method. Pyschometrika 29, 115--129.
• 18: Linial, N. 2002. Finite metric spaces—Combinatorics, geometry and algorithms. In Proceedings of the International Congress of Mathematicians III, 573--586.
• 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: James H. Schmerl , William T. Trotter, Critically indecomposable partially ordered sets, graphs, tournaments and other binary relational structures, Discrete Mathematics, v.113 n.1-3, p.191-205, April 5, 1993 [doi>10.1016/0012-365X(93)90516-V]
• 21: Shepard, R. 1962a. The analysis of proximities: Multidimensional scaling with an unknown distance function 1. Pyschometrika 27, 125--140.
• 22: Shepard, R. 1962b. The analysis of proximities: Multidimensional scaling with an unknown distance function 2. Pyschometrika 27, 216--246.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Pattern matching; Geometrical problems and computations

General Terms:
Algorithms, Theory

Keywords:
Optimal metric embeddings, dynamic programming, forbidden patterns, line embeddings, metric spaces, shape matching