Hardness of embedding metric spaces of equal size

Subhash Khot, Rishi Sake

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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].

Original languageEnglish (US)
Title of host publicationApproximation, Randomization, and Combinatorial Optimization
Subtitle of host publicationAlgorithms and Techniques - 10th International Workshop, APPROX 2007 and 11th International Workshop, RANDOM 2007, Proceedings
PublisherSpringer Verlag
Pages218-227
Number of pages10
ISBN (Print)9783540742074
DOIs
StatePublished - 2007
Event10th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2007 and 11th International Workshop on Randomization and Computation, RANDOM 2007 - Princeton, NJ, United States
Duration: Aug 20 2007Aug 22 2007

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4627 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other10th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2007 and 11th International Workshop on Randomization and Computation, RANDOM 2007
CountryUnited States
CityPrinceton, NJ
Period8/20/078/22/07

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Hardness of embedding metric spaces of equal size'. Together they form a unique fingerprint.

Cite this