@inproceedings{6db1ed7285ef4602a715fdb22daef1b4,

title = "Hardness of embedding metric spaces of equal size",

abstract = "We study the problem embedding an n-point metric space into another n-point metric space while minimizing distortion. We show that there is no polynomial time algorithm to approximate the minimum distortion within a factor of Ω((log n)1/4-δ) for any constant δ > 0, unless NP ⊆ DTIME(npoly(log n))). We give a simple reduction from the METRIC LABELING problem which was shown to be inapproximable by Chuzhoy and Naor [10].",

author = "Subhash Khot and Rishi Sake",

year = "2007",

doi = "10.1007/978-3-540-74208-1_16",

language = "English (US)",

isbn = "9783540742074",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "218--227",

booktitle = "Approximation, Randomization, and Combinatorial Optimization",

note = "10th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2007 and 11th International Workshop on Randomization and Computation, RANDOM 2007 ; Conference date: 20-08-2007 Through 22-08-2007",

}