Anzeige
Erschienen in:
2005 | OriginalPaper | Buchkapitel
On the Hardness of Embeddings Between Two Finite Metrics
verfasst von : Matthew Cary, Atri Rudra, Ashish Sabharwal
Erschienen in: Automata, Languages and Programming
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We improve hardness results for the problem of embedding one finite metric into another with minimum distortion. This problem is equivalent to optimally embedding one weighted graph into another under the shortest path metric. We show that unless
P
=
NP
, the minimum distortion of embedding one such graph into another cannot be efficiently approximated within a factor less than 9/4 even when the two graphs are unweighted trees. For weighted trees with the ratio of maximum edge weight to the minimum edge weight of
α
2
(
α
≥ 1) and all but one node of constant degree, we improve this factor to 1+
α
. We also obtain similar hardness results for extremely simple line graphs (weighted). This improves and complements recent results of Kenyon et al.[13] and Papadimitriou and Safra [18].