Metric space embeddings into l(1): an optimization approach
Moses Charikar, Bo Brinkman · 2004
The technique of metric space embeddings into Euclidean space has been used extensively to give powerful approximation algorithms for a variety of problems. Much of the success of this technique has been due to the famous lemma of Johnson and Lindenstrauss which says that any n points in Euclidean space can be well approximated by vectors of length roughly O(log n) via random projections. Embeddings into Euclidean space, however, are known to be somewhat limited: For example, there are planar graph metrics which require Wlogn distortion in Euclidean space. Finite metric spaces in Rd under the e1 norm arise in practice as well, and it is known that for embedding this is a strictly richer class of metrics than the finite Euclidean metrics. This has motivated an interest in e 1 as a possible host space for difficult metrics, particularly edit metrics and planar graph metrics. We have developed an approach to the study of e1 embeddings based on mathematical optimization. We show how these techniques, through duality, lead naturally to both lower bounds and algorithms. We demonstrate this approach by proving that no analogue of the Johnson-Lindenstrauss lemma exists for e1. This answers the open question recently popularized by both Piotr Indyk and Nathan Linial. This work is available online at http://www.derandomized.org/ .