Published on *Computer Science Department at Princeton University* (http://www.cs.princeton.edu)

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 roughlyO(log n) via random projections.

m

Embeddings into Euclidean space, however, are known to be somewhat

limited: For example, there are planar graph metrics which require

Ω(√log n) distortion in Euclidean space.

Finite metric spaces in Rd

under thel1 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 inl1 as a possible

host space for difficult metrics, particularly edit metrics and planar

graph metrics.We have developed an approach to the study of

l1 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 forl1. This answers the open

question recently popularized by both Piotr Indyk and Nathan Linial.