Skip to Main Content

Transactions of the American Mathematical Society

Published by the American Mathematical Society since 1900, Transactions of the American Mathematical Society is devoted to longer research articles in all areas of pure and applied mathematics.

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

The 2020 MCQ for Transactions of the American Mathematical Society is 1.48.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

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
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
  • 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