@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",
}