Inapproximability for Metric Embeddings into R^d
Jiřı́ Matoušek, Anastasios Sidiropoulos · 2008
We consider the problem of computing the smallest possible distortion for embedding of a given n-point metric space into 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 n1/12is NP-hard. From this result we derive inapproximability with factor roughly n1/(22d-10)for every fixed d ges 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 Vaisala). For d ges 3,we obtain a stronger inapproximability result by a different reduction: assuming PneNP, no polynomial- time algorithm can distinguish between spaces embeddable in R.d with constant distortion from spaces requiring distortion at least nc/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 Rdwith distortion O(n2/dlog3/2n) 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 R2, while all not too large subspaces of it embed almost isometrically.