Inapproximability for metric embeddings into $\mathbb {R}^d$
HTML articles powered by AMS MathViewer
- by Jiří Matoušek and Anastasios Sidiropoulos PDF
- Trans. Amer. Math. Soc. 362 (2010), 6341-6365 Request permission
Abstract:
We consider the problem of computing the smallest possible distortion for embedding of a given $n$-point metric space into $\mathbb {R}^d$, where $d$ is fixed (and small). For $d=1$, it was known that approximating the minimum distortion with a factor better than roughly $n^{1/12}$ is NP-hard. From this result we derive inapproximability with a factor roughly $n^{1/(22d-10)}$ for every fixed $d\ge 2$, by a conceptually very simple reduction. However, the proof of correctness involves a nontrivial result in geometric topology (whose current proof is based on ideas due to Jussi Väisälä).
For $d\ge 3$, we obtain a stronger inapproximability result by a different reduction: assuming P$\ne$NP, no polynomial-time algorithm can distinguish between spaces embeddable in $\mathbb {R}^d$ with constant distortion from spaces requiring distortion at least $n^{c/d}$, for a constant $c>0$. The exponent $c/d$ has the correct order of magnitude, since every $n$-point metric space can be embedded in $\mathbb {R}^d$ with distortion $O(n^{2/d}\log ^{3/2}n)$ and such an embedding can be constructed in polynomial time by random projection.
For $d=2$, we give an example of a metric space that requires a large distortion for embedding in $\mathbb {R}^2$, while all not too large subspaces of it embed almost isometrically.
References
- Sanjeev Arora, László Lovász, Ilan Newman, Yuval Rabani, Yuri Rabinovich, and Santosh Vempala, Local versus global properties of metric spaces (extended abstract), Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, ACM, New York, 2006, pp. 41–50. MR 2360119, DOI 10.1145/1109557.1109563
- Robert Babilon, Jiří Matoušek, Jana Maxová, and Pavel Valtr, Low-distortion embeddings of trees, J. Graph Algorithms Appl. 7 (2003), no. 4, 399–409. MR 2114084, DOI 10.7155/jgaa.00076
- MohammadHossein Bateni, Erik D. Demaine, MohammadTaghi Hajiaghayi, and Mohammad Moharrami, Plane embeddings of planar graph metrics, Discrete Comput. Geom. 38 (2007), no. 3, 615–637. MR 2352711, DOI 10.1007/s00454-007-1353-4
- J. Bourgain, On Lipschitz embedding of finite metric spaces in Hilbert space, Israel J. Math. 52 (1985), no. 1-2, 46–52. MR 815600, DOI 10.1007/BF02776078
- Mihai Bădoiu, Julia Chuzhoy, Piotr Indyk, and Anastasios Sidiropoulos, Low-distortion embeddings of general metrics into the line, STOC’05: Proceedings of the 37th Annual ACM Symposium on Theory of Computing, ACM, New York, 2005, pp. 225–233. MR 2181621, DOI 10.1145/1060590.1060624
- Mihai Bădoiu, Julia Chuzhoy, Piotr Indyk, and Anastasios Sidiropoulos, Embedding ultrametrics into low-dimensional spaces, Computational geometry (SCG’06), ACM, New York, 2006, pp. 187–196. MR 2389326, DOI 10.1145/1137856.1137886
- Mihai Bădoiu, Kedar Dhamdhere, Anupam Gupta, Yuri Rabinovich, Harald Räcke, R. Ravi, and Anastasios Sidiropoulos, Approximation algorithms for low-distortion embeddings into low-dimensional spaces, Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, ACM, New York, 2005, pp. 119–128. MR 2298257
- Mihai Bădoiu, Piotr Indyk, and Anastasios Sidiropoulos, Approximation algorithms for embedding general metrics into trees, Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, ACM, New York, 2007, pp. 512–521. MR 2482878
- M. Charikar, K. Makarychev, and Y. Makarychev. Local global tradeoffs in metric embeddings. In Proceedings of 48th Annual IEEE Symposium on Foundations of Computer Science, pages 713–723. IEEE Computer Society, 2007.
- Benny Chor and Madhu Sudan, A geometric approach to betweenness, SIAM J. Discrete Math. 11 (1998), no. 4, 511–523. MR 1640920, DOI 10.1137/S0895480195296221
- Michel Marie Deza and Monique Laurent, Geometry of cuts and metrics, Algorithms and Combinatorics, vol. 15, Springer-Verlag, Berlin, 1997. MR 1460488, DOI 10.1007/978-3-642-04295-9
- A. Gupta, Embedding tree metrics into low-dimensional Euclidean spaces, Discrete Comput. Geom. 24 (2000), no. 1, 105–116. MR 1765236, DOI 10.1145/301250.301434
- Alexander Hall and Christos Papadimitriou, Approximating the distortion, Approximation, randomization and combinatorial optimization, Lecture Notes in Comput. Sci., vol. 3624, Springer, Berlin, 2005, pp. 111–122. MR 2193680, DOI 10.1007/11538462_{1}0
- Piotr Indyk, Algorithmic applications of low-distortion geometric embeddings, 42nd IEEE Symposium on Foundations of Computer Science (Las Vegas, NV, 2001) IEEE Computer Soc., Los Alamitos, CA, 2001, pp. 10–33. MR 1948692
- William B. Johnson and Joram Lindenstrauss, Extensions of Lipschitz mappings into a Hilbert space, Conference in modern analysis and probability (New Haven, Conn., 1982) Contemp. Math., vol. 26, Amer. Math. Soc., Providence, RI, 1984, pp. 189–206. MR 737400, DOI 10.1090/conm/026/737400
- Claire Kenyon, Yuval Rabani, and Alistair Sinclair, Low distortion maps between point sets, Proceedings of the 36th Annual ACM Symposium on Theory of Computing, ACM, New York, 2004, pp. 272–280. MR 2121609, DOI 10.1145/1007352.1007398
- M. D. Kirszbraun. Uber die zusammenziehenden und lipschitzchen Transformationen. Fund. Math., 22:77–108, 1934.
- James R. Lee, Assaf Naor, and Yuval Peres, Trees and Markov convexity, Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, ACM, New York, 2006, pp. 1028–1037. MR 2373829, DOI 10.1145/1109557.1109671
- Nathan Linial, Eran London, and Yuri Rabinovich, The geometry of graphs and some of its algorithmic applications, Combinatorica 15 (1995), no. 2, 215–245. MR 1337355, DOI 10.1007/BF01200757
- Jiří Matoušek, Bi-Lipschitz embeddings into low-dimensional Euclidean spaces, Comment. Math. Univ. Carolin. 31 (1990), no. 3, 589–600. MR 1078491
- Karl Menger, New Foundation of Euclidean Geometry, Amer. J. Math. 53 (1931), no. 4, 721–745. MR 1506850, DOI 10.2307/2371222
- James R. Munkres, Elements of algebraic topology, Addison-Wesley Publishing Company, Menlo Park, CA, 1984. MR 755006
- Krzysztof Onak and Anastasios Sidiropoulos, Circular partitions with applications to visualization and embeddings, Computational geometry (SCG’08), ACM, New York, 2008, pp. 28–37. MR 2504268, DOI 10.1145/1377676.1377683
- J. Opatrný, Total ordering problem, SIAM J. Comput. 8 (1979), no. 1, 111–114. MR 522973, DOI 10.1137/0208008
- Christos Papadimitriou and Shmuel Safra, The complexity of low-distortion embeddings between point sets, Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, ACM, New York, 2005, pp. 112–118. MR 2298256
- J. Väisälä. Holes and weakly bilipschitz maps. Manuscript, 3 pages, 2008.
Additional Information
- Jiří Matoušek
- Affiliation: Department of Applied Mathematics and Institute of Theoretical Computer Science (ITI), Charles University, Malostranské nám. 25, 118 00 Praha 1, Czech Republic
- Email: matousek@kam.mff.cuni.cz
- Anastasios Sidiropoulos
- Affiliation: Department of Computer Science, University of Toronto, 10 King’s College Road, SF 2302A, Toronto, Ontario, Canada M5S 3G4
- Address at time of publication: Toyota Technological Institute at Chicago, 6045 S. Kenwood Avenue, Office 421, Chicago, Illinois 60637
- Email: tasoss@cs.toronto.edu, tasos@ttic.edu
- Received by editor(s): July 15, 2008
- Published electronically: July 14, 2010
- © Copyright 2010
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication. - Journal: Trans. Amer. Math. Soc. 362 (2010), 6341-6365
- MSC (2010): Primary 68Q17
- DOI: https://doi.org/10.1090/S0002-9947-2010-05186-4
- MathSciNet review: 2678977