Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)



Inapproximability for metric embeddings into $ \mathbb{R}^d$

Authors: Jiří Matoušek and Anastasios Sidiropoulos
Journal: Trans. Amer. Math. Soc. 362 (2010), 6341-6365
MSC (2010): Primary 68Q17
Published electronically: July 14, 2010
MathSciNet review: 2678977
Full-text PDF

Abstract | References | Similar Articles | Additional Information


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 [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2010): 68Q17

Retrieve articles in all journals with MSC (2010): 68Q17

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

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

Received by editor(s): July 15, 2008
Published electronically: July 14, 2010
Article copyright: © Copyright 2010 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society