ECCC-Report TR07-108https://eccc.weizmann.ac.il/report/2007/108Comments and Revisions published for TR07-108en-usMon, 29 Oct 2007 02:45:12 +0200
Paper TR07-108
| Local Global Tradeoffs in Metric Embeddings |
Moses Charikar,
Konstantin Makarychev,
Yury Makarychev
https://eccc.weizmann.ac.il/report/2007/108Suppose that every k points in a n point metric space X are D-distortion embeddable into l_1. We give upper and lower bounds on the distortion required to embed the entire space X into l_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 l_1 with distortion O(D log (n/k)). Moreover, we give a lower bound showing that this result is tight if D is bounded away from 1. For D = 1+delta we give a lower bound of Omega(log (n/k) / log (1/delta)); and for D = 1, we give a lower bound of Omega(log n /(log k + log log n)).
Our bounds significantly improve on the results of Arora, Lovasz, Newman, Rabani, Rabinovich and Vempala, who initiated a study of these questions.
Mon, 29 Oct 2007 02:45:12 +0200https://eccc.weizmann.ac.il/report/2007/108