Inapproximability for metric embeddings into $\mathbb{R}^{d}$
Jiřı́ Matoušek, Anastasios Sidiropoulos · Transactions of the American Mathematical Society · 2010
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$ e$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.