Inapproximability for metric embeddings into Rᵈ

الأصل · EN

We consider the problem of computing the smallest possible distortion for embedding of a given n-point metric space into Rᵈ, 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 factor roughly n(1/(22d-10)) for every fixed d≥ 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≥ 3, we obtain a stronger inapproximability result by a different reduction: assuming P ≠ NP, no polynomial-time algorithm can distinguish between spaces embeddable in Rᵈ 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 Rᵈ with distortion O(n²/ᵈ³/²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 R², while all not too large subspaces of it embed almost isometrically.