TY - GEN

T1 - Local global tradeoffs in metric embeddings

AU - Charikar, Moses

AU - Makarychev, Konstantin

AU - Makarychev, Yury

PY - 2007/12/1

Y1 - 2007/12/1

N2 - Suppose that every k points in a metric space X are D-distortion embeddable into ℓ1. We give upper and lower bounds on the distortion required to embed the entire space X into ℓ1. This is a natural mathematical question and is also motivated by the study of relaxations obtained by lift-and-project methods for graph partitioning problems. In this setting, we show that X can be embedded into ℓ1 with distortion O(D × log(|X|/k)). Moreover, we give a lower bound showing that this result is tight if D is bounded away from 1. For D = 1 + δ we give a lower bound of Ω(log(|X|/k)/ log(1/δ)); and for D = 1, we give a lower bound of Ω(log |X| / (log k+log log |X|)). Our bounds significantly improve on the results of Arora, Lovász, Newman, Rabani, Rabinovich and Vempala, who initiated a study of these questions.

AB - Suppose that every k points in a metric space X are D-distortion embeddable into ℓ1. We give upper and lower bounds on the distortion required to embed the entire space X into ℓ1. This is a natural mathematical question and is also motivated by the study of relaxations obtained by lift-and-project methods for graph partitioning problems. In this setting, we show that X can be embedded into ℓ1 with distortion O(D × log(|X|/k)). Moreover, we give a lower bound showing that this result is tight if D is bounded away from 1. For D = 1 + δ we give a lower bound of Ω(log(|X|/k)/ log(1/δ)); and for D = 1, we give a lower bound of Ω(log |X| / (log k+log log |X|)). Our bounds significantly improve on the results of Arora, Lovász, Newman, Rabani, Rabinovich and Vempala, who initiated a study of these questions.

UR - http://www.scopus.com/inward/record.url?scp=45749095867&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=45749095867&partnerID=8YFLogxK

U2 - 10.1109/FOCS.2007.4389539

DO - 10.1109/FOCS.2007.4389539

M3 - Conference contribution

AN - SCOPUS:45749095867

SN - 0769530109

SN - 9780769530109

T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

SP - 713

EP - 723

BT - Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2007

T2 - 48th Annual Symposium on Foundations of Computer Science, FOCS 2007

Y2 - 20 October 2007 through 23 October 2007

ER -