Inapproximability for planar embedding problems
Jeff A. Edmonds, Anastasios Sidiropoulos, Anastasios Zouzias · 2009
We consider the problem of computing a minimumdistortion bijection between two point-sets in R 2.Weprove the first non-trivial inapproximability result for this problem, for the case when the distortion is constant. More precisely, we show that there exist constants 0 <α<β, such that it is NP-hard to distinguish between spaces for which the distortion is either at most α, oratleastβ, under the Euclidean norm. This addresses a question of Kenyon, Rabani and Sinclair [KRS04], and extends a result due to Papadimitriou and Safra [PS05], who gave inapproximability for point-sets in R 3. We also apply similar ideas to the problem of computing a minimum-distortion embedding of a finite metric space into R 2. We obtain an analogous inapproximability result under the ℓ ∞ norm for this problem. Inapproximability for the case of constant distortion was previously known only for dimension at least 3 [MS08]. 1