---
abstract: |
    Finite metric spaces arise in many different contexts. Enormous bodies of data, scientific, commercial and others can often be viewed as large metric spaces. It turns out that the metric of graphs reveals a lot of interesting information. Metric spaces also come up in many recent advances in the theory of algorithms. Finally, finite submetrics of classical geometric objects such as normed spaces or manifolds reflect many important properties of the underlying structure. In this paper we review some of the recent advances in this area.

    4.5mm

    [**2000 Mathematics Subject Classification:**]{} Combinatorics, Algorithms, Geometry.

    [**Keywords and Phrases:**]{} Finite metric spaces, Distortion, graph, Normed space, Approximation algorithms.
author:
- 'Nathan Linial[^1]'
title: '**Finite Metric Spaces—Combinatorics,-2mm Geometry and Algorithms**'
---

Introduction
============

-5mm

The constantly intensifying ties between combinatorics and geometry are among the most significant developments in Discrete Mathematics in recent years. These connections are manifold, and it is, perhaps, still too early to fully evaluate this relationship. This article deals only with what might be called [*the geometrization of combinatorics*]{}. Namely, the idea that viewing combinatorial objects from a geometric perspective often yields unexpected insights. Even more concretely, we concentrate on finite metric spaces and their embeddings.

To illustrate the underlying idea, it may be best to begin with a practical problem. There are many disciplines, scientific, technological, economic and others, which crucially depend on the analysis of large bodies of data. Technological advances have made it possible to collect enormous amounts of interesting data, and further progress depends on our ability to organize and classify these data so as to allow meaningful and insightful analysis. A case in point is bioinformatics where huge bodies of data - DNA sequences, protein sequences, information about expression levels etc. all await analysis. Let us consider, for example, the space of all proteins. For the purpose of the current discussion, a protein may be viewed as a word in an alphabet of 20 letters (amino acids). Word lengths vary from under fifty to several thousands, the most typical length being several hundred letters. At this writing, there are about half a million proteins whose sequence is known. Algorithms were developed over the years to evaluate the similarity of different proteins, and there are standard computer programs that calculate distances among proteins very efficiently. This turns the collection of all known proteins into a metric space of about half a million elements. Proper analysis of this space is of great importance for the biological sciences. Thus, this huge body of sequence data takes a geometric form, namely, a finite metric space, and it becomes feasible to use geometric concepts and tools in the analysis of this data.

In the combinatorial realm proper, and in the design and analysis of algorithms, similar ideas have proved very useful as well. A graph is completely characterized by its (shortest path, or geodesic) metric. The analysis of this metric provides a lot of useful information about the graph. Moreover, given a graph $G$, one may modify $G$’s metric by assigning nonnegative [*lengths*]{} to $G$’s edges. By varying these edge lengths, a family of finite metrics is obtained, the properties of which reflect a good deal of structural information about $G$. We mention in passing that there are other useful and interesting geometric viewpoints of graphs. Thus, it is useful to geometrically realize a graph by assigning vectors to the vertices and posit that adjacent vertices correspond to orthogonal vectors. Graphs can encode the intersection patterns of geometric objects. These are all interesting instances of our basic paradigm: In the study of combinatorial objects, and especially graphs, it is often beneficial to develop a perspective from which the graph is perceived geometrically.

Aside from what has already been thus accomplished, this approach holds a great promise. Combinatorics as we know it, is still a very young subject. (There is no official date of birth, and Euler was undoubtedly a giant in our field, but I think that the dawn of modern combinatorics can be dated to the 1930’s). Discrete Mathematics stands to gain a lot from interactions with older, better established fields. This geometrization of combinatorics indeed creates clear and tangible connections with various subfields of geometry. So far the study of finite metric spaces has had substantial connections with the theory of finite-dimensional normed spaces, but it seems safe to predict that useful ties with differential geometry will soon emerge. With the possible incorporation of probabilistic tools, now commonplace in combinatorics, we can expect very exciting outcomes.

A good sign for the vitality of this area is the large number of intriguing open problems. We will present here some of those that we particularly like. In a recent meeting (Haifa, March ’02), a list of open problems in this area has been collected, see http://www.kam.mff.cuni.cz/$\tilde{}$matousek/haifaop.ps. More extensive surveys of this area can be found in [@matousek_disc_geom] Chapter 15, and [@Ind_surv].

In view of this description, it should not come as a surprise to the reader that this theory is characterized as being

-   [*Asymptotic:*]{} We are mostly interested in analyzing large, finite metric spaces, graphs and data sets.

-   [*Approximate:*]{} While it is possible to postulate that the geometric situation agrees perfectly with the combinatorics, it is much more beneficial to investigate the approximate version. This leads to a richer theory that is quantitative in nature. Rather than a binary question whether perfect mimicking is possible or not, we ask [*how well*]{} a given combinatorial object can be approximated geometrically.

-   [*Algorithmic:*]{} Existential results are very important and interesting in this area, but we always prefer it when such a result is accompanied by an efficient algorithm.

-   It is mostly [*comparative:*]{} There are certain classes of finite metric spaces that we favor. These may have a particularly simple structure or be very well understood. Other, less well behaved spaces are being compared to, and approximated by, these “nice" metrics.

So, how should we compare between two metrics? Let $(X,d)$ and $(Y,\rho)$ be two metric spaces and let $\varphi: X \rightarrow Y$ be a mapping between them. We quantify the extent to which $\varphi$ expands, resp. contracts distances: ${\mbox{expansion}}(\varphi)
= \sup_{x,y \in X} \frac{\rho(\varphi(x),\varphi(y))}{d(x,y)}$ and ${\mbox{contraction}}(\varphi) = \sup_{x,y \in X}
\frac{d(x,y)}{\rho(\varphi(x),\varphi(y))}$.

Finally, the main definition is: ${\mbox{distortion}}(\varphi) =
{\mbox{expansion}}(\varphi) \cdot {\mbox{contraction}}(\varphi)$.

In other words, we consider the tightest constants $\alpha \ge
\beta$ for which $\alpha \ge
\frac{\rho(\varphi(x),\varphi(y))}{d(x,y)} \ge \beta$ always holds, and define ${\mbox{distortion}}(\varphi)$ as $\frac{\alpha}{\beta}$. We call $\varphi$ an [*isometry*]{} when ${\mbox{distortion}}(\varphi) = 1$. This deviates somewhat from the conventional definition, and a map that multiplies all distances by a constant (not necessarily $1$) is being considered here as an isometry.

The least distortion with which $(X,d)$ can be embedded in $(Y,\rho)$ is denoted $c_Y(X)=c_Y(X,d)$. If $\cal C$ is a class of metric spaces, then the infimum of $c_Y(X)$ over all $Y \in \cal
C$ is denoted by $c_{\cal C}(X)$. When $\cal C$ is the class of finite-dimensional $l_p$ spaces $\{l_p^n | n=1,2,\dots\}$ we denote $c_{\cal C}(X)$ by $c_p(X)$.

One of the [**major problems**]{} in this area is:

Given a finite metric space $(X,d)$ and a class of metrics $\cal C$, find the (nearly) best approximation for $X$ by a metric from $\cal C$. In other words, find a metric space $Y \in \cal C$ and a map $\varphi: X \rightarrow Y$ such that ${\mbox{distortion}}(\varphi)$ (nearly) equals $c_{\cal C}(X)$.

The classes of metric spaces $\cal C$ for which this problem has so far been studied are: (i) Metrics of normed spaces, especially $l_p^n$ for $\infty \ge p \ge 1$ and $n=1,2,\ldots$. (ii) Metrics of special families of graphs, most notably trees, as well as convex combinations thereof.

One more convention: Speaking of $l_p$, either means infinite dimensional $l_p$, or, what is often the same, that we do not care about the dimension of the space in which we embed a given metric.

To get a first feeling for this subject, let us consider the smallest nontrivial example. Every $3$-point metric embeds isometrically into the plane, but as we show now, the metric of $K_{1,3}$, the $4$-vertex tree with a root and three leaves, has no isometric embedding into $l_2$. Let $x$, resp. $y_i$ be the image of the root and the leaves of this tree. Since $d(x,y_i)=1$ and $d(y_i,y_j)=2$ for all $i \ne j$, it follows that the three points $x,y_i,y_j$ are colinear for every $i \ne j$. Thus, all four points are colinear, leading to a contradiction. It can be shown that the least distorted image of this graph in $l_2$ is in the plane with $120^{\circ}$ degree angle among the edges. Below (Section \[sec\_l2\]) we present a polynomial-time algorithm that determines $c_2(X)$, the least $l_2$ distortion for any finite metric $(X,d)$.

Another easy fact which belongs into this warm-up section is that $c_{\infty}(X) = 1$ for every finite metric $(X,d)$. That is, the space $l_{\infty}$ space contains an isometric copy of every finite metric space.\
[**Acknowledgment:**]{} Helpful remarks on this article by R. Krauthgamer, A. Magen, J. Matou[š]{}ek, and Yu. Rabinovich are gratefully acknowledged.

Embedding into [$l_2$]{} {#sec_l2}
========================

-5mm

This is by far the most developed part of the theory. There are several good reasons for this part of the theory to have attracted the most attention so far. Consider the practical context, where a metric space represents some large data set, and where the major driving force is the search for good algorithms for data analysis. If the data set you need to analyze happens to be a large set of points in $l_2$, there are many tools at your disposal, from geometry, algebra and analysis. So if your data can be well approximated in $l_2$, this is of great practical advantage. There is another reason for the special status of $l_2$ in this area. To explain it, we need to introduce some terminology from Banach space theory. The [*Banach-Mazur distance*]{} among two normed spaces $X$ and $Y$, is said to be $\le c$, if there is a [*linear*]{} map $\varphi: X \rightarrow Y$ with ${\mbox{distortion}}(\varphi) \le c$. What we are doing here may very well be described as a search for the metric counterpart of this highly developed linear theory. See [@MS86] for an introduction to this field and [@BeLin] for a comprehensive cover of the nonlinear theory. The grandfather of the linear theory is the celebrated theorem of Dvoretzky [@dvor].

\[dvoretzky\] For every $n$ and $\epsilon >0$, every $n$-dimensional normed space contains a $k=\Omega(\epsilon^2 \cdot
\log n)$-dimensional space whose Banach-Mazur distance from $l_2$ is $\le 1+\epsilon$.

Thus, among embeddings into normed spaces, embeddings into $l_2$ are the hardest to come by.

We begin our story with an important theorem of Bourgain [@Bourgain85].

\[bour\_thm\] Every $n$-point metric space [^2] embeds in $l_2$ with distortion $\le O(\log n)$.

Not only is this a fundamental result, Bourgain’s proof of the theorem readily translates into an efficient randomized algorithm that finds, for any given finite $(X,d)$ an embedding in $l_2$ of distortion $\le O(\log n)$. The algorithm is so simple that we record it here. Given the metric space $(X,d)$, we map every point $x \in X$ to $\varphi(x)$, an $O(\log^2 n)$-dimensional vector. Coordinates in $\varphi(\cdot)$ correspond to subsets $S \subseteq
X$, and the $S$-th coordinate in $\varphi(x)$ is simply $d(x,S)$, the minimum of $d(x,y)$ over all $y \in S$. To define the map $\varphi$, we need to specify, then, the collection of subsets $S$ that we utilize. These sets are selected randomly. Namely, you randomly select $O(\log n)$ sets of size $1$, another $O(\log n)$ sets of size $2$, of size $4, 8...,\frac{n}{2}$.

In view of Bourgain’s Theorem, several questions suggest themselves naturally:

-   Is this bound tight? The answer is positive, see Theorem \[expander\].

-   Given that $\max c_2(X)$ over all $n$-point metrics is $\Theta(\log n)$, what about metrics that are closer to $l_2$? Is there a polynomial-time algorithm to compute $c_2(X,d)$ (That is, the least distortion in an embedding of $X$ into $l_2$)? Again the answer is affirmative, see below and Theorem \[sdp\].

-   Are there interesting families of metric spaces for which $c_2$ is substantially smaller than $\log n$? Indeed, there are, see, e.g., Theorem \[tree\].

So let us proceed with the answers to these questions. [*Expanders*]{} are graphs which cannot be disconnected into two large subgraphs by removing relatively few edges. Specifically, a graph $G$ on $n$ vertices is said to be an $\epsilon$-[*(edge)-expander*]{} if, for every set $S$ of $\le n/2$ vertices, there are at least $\epsilon |S|$ edges between $S$ and its complement. It is said to be $k$-[*regular*]{} if every vertex has exactly $k$ neighbors. The theory of expander graphs is a fascinating chapter in discrete mathematics and theoretical computer science. It is not obvious that arbitrarily large $k$-regular graphs exist with expansion $\epsilon$ bounded away from zero. In fact, in the early days of this area, conjectures to the contrary had been made. It turns out, however, that expanders are rather ubiquitous. For every $k \ge 3$, the probability that a randomly chosen $k$-regular graph has expansion $\epsilon > k/10$ tends to $1$ as the number of vertices $n$ tends to $\infty$. It turns out that the metrics of expander graphs are as far from $l_2$ as possible. [^3]

\[expander\] Let $G$ be an $n$-vertex $k$-regular $\epsilon$-expander graph ($k \ge 3$, $\epsilon >0$). Then $c_2(G)
\ge c \log n$ where $c$ depends only on $k$ and $\epsilon$.

Metric geometry is by no means a new subject, and indeed metrics that embed isometrically into $l_2$ were characterized long ago (see e.g. [@Blumenthal]). This is a special case of the more recent results. Let $\varphi: X \rightarrow l_2^n$ be an embedding. The condition that ${\mbox{distortion}}(\varphi) \le c$ can be expressed as a system of linear inequalities in the entries of the Gram matrix corresponding to the vectors in $\varphi(X)$. Therefore, the computation of $c_2(X)$ is an instance of [*semidefinite quadratic programming*]{} and can be found in polynomial time. [^4] This formulation of the problem has, however, other useful consequences. The duality principle of convex programming yields a max-min formula for $c_2$.

\[sdp\] For every finite metric space $(X,d)$, $$c_2(X,d) = \max \sqrt{{\frac{\sum_{i,j:q_{i,j} >
0}d^2(i,j)q_{i,j}}
  {\sum_{i,j:q_{i,j}  <  0}d^2(i,j)|q_{i,j}|}}},$$ where the maximum is over all matrices $Q$ so that

1.  $Q$ is positive semidefinite, and

2.  The entries in every row in $Q$ sum to zero.

Consider the metric of the $r$-dimensional cube. As shown by Enflo [@Enflo69], the least distorted embedding of this metric is simply the identity map into $l_2^r$, which has distortion $\sqrt{r}$. Our first illustration for the power of the quadratic programming method is that we provide a quick elementary proof for this fact, earlier proofs of which required heavier machinery. The rows and columns of the matrix $Q$ are indexed by the $2^r$ vertices of the $r$-dimensional cube. The $(x,y)$ entry of $Q$ is: (i) $r-1$ if $x=y$, (ii) It is $-1$ if $x$ and $y$ are neighbors (they are represented by two $0,1$ vectors that differ in exactly one coordinate, and (iii) It is $1$ if $x$ and $y$ are antipodal, i.e., they differ in all $r$ coordinates. (iv) All other entries of $Q$ are zero. We leave out the details and only indicate how to prove that $Q$ is positive semidefinite. It is possible to express $Q=(r-1)I - A + P$, where $A$ is the adjacency matrix of the $r$-cube and $P$ is the (permutation) matrix corresponding to being antipodal. The eigenfunctions of $A$ are well known, namely, they are the $2^r$ Walsh functions. The same vectors happen to be also the eigenvectors of $Q$ and all have nonnegative eigenvalues.

As another application of this method (also from [@LM00]), here is a quick proof of Theorem \[expander\]. It is known [@Alon_eigen_expan] that if $G$ is a $k$-regular $\epsilon$-expander graph and $A$ is $G$’s adjacency matrix, then the second eigenvalue of $A$ is $<k - \delta$ for some $\delta$ that depends on $k$ and $\epsilon$, but not on the size of the graph [^5]. It is not hard to show that the vertices of a graph with bounded degrees can be paired up so that every two paired vertices are at distance $\Omega(\log n)$. Let $P$ be the permutation matrix corresponding to such a pairing. It is not hard to establish Theorem \[expander\] using the matrix $Q = kI - A + \frac{\delta}{2} (P-I)$. More sophisticated applications of this method will be described below (Theorem \[girth\_l2\]).

Specific families of graph metrics
==================================

-5mm

For various graph families, it is possible find embeddings into $l_2$ with distortion asymptotically smaller than $\log n$. This often applies as well to graphs with arbitrary nonnegative edge lengths.

Trees
-----

-5mm

The metrics of trees are quite restricted. They can be characterized through a four-term inequality (e.g. [@deza_lau]). It is also not hard to see that every tree metric embeds isometrically into $l_1$. They can also be embedded into $l_2$ with a relatively low distortion.

\[tree\] Every tree on $n$ vertices can be embedded into $l_2$ with distortion $\le O(\sqrt{\log \log n})$.

Bourgain [@Bourgain86] had earlier shown that this bound is attained for complete binary trees. (See [@Li:Sa_tree] for an elementary proof of this.)

Planar graphs
-------------

-5mm

It turns out that the metrics of planar graphs have good embedding into $l_2$. Rao [@Rao99] showed:

\[rao\_thm\] Every planar graph embeds in $l_2$ with distortion $O(\sqrt{\log n})$.

A recent construction of Newman and Rabinovich [@RabinovichNewmanSoCG] shows that this bound is tight.

Graphs of high girth
--------------------

-5mm

The [*girth*]{} of a graph is the length of the shortest cycle in the graph. If you restrict your attention (as we do in this section) to graphs in which all vertex degrees are $\ge 3$, then it is still a major challenge to construct graphs with very high girth, i.e., having no short cycles. The metrics of such graphs seem far from $l_2$, so in [@LLR95] it was conjectured that $c_2(G) \ge \Omega(g)$ for every graph $G$ of girth $g$ in which all vertex degrees are $\ge 3$. There are known examples of $n$-vertex $k$-regular expanders whose girth is $\Omega(\log n)$. In view of Theorem \[bour\_thm\], such graphs show that this conjecture, if true, is best possible. Recently, the following was shown:

\[girth\_l2\] Let $G$ be a $k$-regular graph $k \ge 3$ with girth $g$. Then $c_2(G) \ge \Omega(\sqrt{g})$.

Two proofs of this theorem are given in [@LiMaNa_girth]. One is based on the notion of [*Markov Type*]{} due to Ball [@ball_markov_type]. The underlying idea of this proof is that a random walk on a graph with girth $g$ and all vertex degree $\ge 3$ drifts at a constant speed away from its starting point for time $\Omega(g)$. On the other hand, in an appropriately defined class of random walks in Euclidean space, at time $T$ the walk is expected to be only $O(\sqrt{T})$ away from its origin. If we compare between the graph itself and its image under an embedding in $l_2$, this discrepancy must be accounted for by a metrical distortion. The comparison at time $T = \Theta(g)$ yields a distortion of $\Omega(\sqrt{g})$.

The other proof again employs semidefinite programming, using the matrix $Q=\alpha I - A + \beta B$. Here $A$ is the graph’s adjacency matrix, and $B$ is a $0,1$ matrix where $B_{xy} = 1$ if $x$ and $y$ are at distance $g/2$ in $G$. The parameters $\alpha$ and $\beta$ have to satisfy the two conditions from Theorem \[sdp\]. A key observation is that due to the high girth, $B$ can be expressed as $P_{g/2}(A)$ where $P_j$ is the $j$-th [*Geronimus Polynomial*]{}, a known family of orthogonal polynomials. The proof depends on the distribution of zeros for these polynomials, and other analytical properties that they have.

Our present state of knowledge leads us to ask:

How small can $c_2(G)$ be for a a graph $G$ of girth $g$ in which all vertices have degree $\ge 3$? The answer lies between $\Omega(\sqrt{g})$ and $O(g)$.

An earlier result of Rabinovich and Raz [@Rab:Raz] reveals another connection between high girth and distortion. Let $\varphi$ be a map from a graph of girth $g$ to a graph of smaller [*Euler characteristic*]{} ($|E|-|V|+1$). Then ${\mbox{distortion}}(\varphi) \ge \Omega(g)$.

Algorithmic applications {#alg_sec}
========================

-5mm

Among the most pleasing aspects of this field, are the many beautiful applications it has to the design of new algorithms.

Multicommodity flow and sparsest cuts
-------------------------------------

-5mm

Flows in networks are a classical subject in discrete optimization and a topic of many investigations (see [@schrijver] for a comprehensive coverage). You are given a [*network*]{} i.e., a graph with two specified vertices: The [*source*]{} $s$ and the [*sink*]{} $t$. Edges have nonnegative [*capacities*]{}. The objective is to ship as much of a given commodity between $s$ and $t$, subject to two conditions: (i) In every vertex other than $s$ and $t$, matter is conserved, (ii) The flow through any edge must not exceed the edge capacity. Let the set $S$ [*separate*]{} the vertices $s$ and $t$, i.e., it contains exactly one of them. Define $S$’s [*capacity*]{} as the sum of edge capacities over those edges that connect $S$ to its complement. The [*Max-flow Min-cut*]{} Theorem states that the largest possible flow equals the minimum such capacity.

Here we consider the $k$-[*commodity*]{} version: Now there are $k$ source-sink pairs $s_i, t_i, i=1,2,...,k$ for the $i$-th commodity, and the $i$-th [*demand*]{} is $D_i >0$. We seek to determine the largest $\phi > 0$ for which it is possible to flow $\phi \cdot D_i$ of the $i$-th commodity between $s_i$ and $t_i$, simultaneously for all $k \ge i \ge 1$ subject to conditions (i) and (ii) above where in (ii) the [*total*]{} flow through an edge should not exceed its capacity. With every subset of the vertices $S$ we associate $\gamma(S)=\frac{\mbox{cap}(S)}{\mbox{dem}(S)}$. As before, $\mbox{cap}(S)$ is the sum of the capacities of edges between $S$ and its complement. The denominator $\mbox{dem}(S)$ is $\sum D_i$ over all indices $i$ so that $S$ separates $s_i$ and $t_i$. It is trivially true that $\phi \le \gamma(S)$, for every flow and every set $S$, but unlike the one-commodity case, $\min
\gamma(S)$ (the [*sparsest cut*]{}) need not equal $\max \phi$. As for the algorithmic perspective, finding $\max \phi$ is a linear program, so it can be computed in polynomial time. However, it is $NP$-hard to determine the sparsest cut. Also, it is interesting to find out how far $\max \phi$ and $\min \gamma(S)$ can be. Consider the case where the underlying graph is an expander, edges have unit capacities and every pair of vertices form a source-sink pair with a unit demand. It is not hard to see that in this case $\phi \le O(\frac{\min \gamma(S)}{\log n})$. On the other hand,

\[multicommodity\] In the $k$-commodity problem $$\max \phi \ge \Omega(\frac{\min \gamma(S)}{\log k}).$$

We will be able to review the proof in Section \[section\_l1\].

Graph bandwidth
---------------

-5mm

In this computational problem, we are presented with an $n$-vertex graph $G$. It is required to label the vertices with distinct labels from $\{1,\ldots,n\}$ so that the difference between the labels of any two adjacent vertices is not too big. Namely, $$\mbox{bw}(G) = \min_{\psi} \max_{xy \in E(G)} |\psi(x) - \psi(y)|,$$ where the minimum is over all $1:1$ maps $\psi: V \rightarrow
\{1,\ldots,n\}$.

It is $NP$-hard to compute this parameter, and for many years no decent approximation algorithm was known. However, a recent paper by Feige [@Feige00] provides a polylogarithmic approximation for the bandwidth. The statement of his algorithm is simple enough to be recorded here:

1.  Compute (a slight modification of) the embedding $\varphi: G
    \rightarrow l_2$ that appears in the proof of Bourgain’s Theorem \[bour\_thm\].

2.  Select a random line $l$ and project $\varphi(G)$ onto it.

3.  Label the vertices of $G$ by the order at which their images appear along the line $l$.

Let $\beta(G) := \max_{x,r} \frac{|B_r(x)|}{r}$ where $B_r(x)$ is the set of those vertices in $G$ at distance $\le r$ from $x$. It’s easy to see that $\mbox{bw}(G) \ge \Omega(\beta(G))$ and an interesting feature of Feige’s proof is that it shows that $\mbox{bw}(G) \le O(\beta(G)\log^c n)$. His paper gives $c=3.5$ which was later [@vemp_dun] improved to $c=3$.

Is it true that $\mbox{bw}(G) \le O(\beta(G)\log n)$?

It is not hard to see that this bound would be tight for expanders.

Bartal’s method {#sect_bartal}
---------------

-5mm

The following general structure theorem of Bartal [@bartal_trees] has numerous algorithmic applications:

\[bartal\] For every finite metric space $(X,d)$ there is a collection of trees $\{T_i~|~i \in I\}$, each of which has $X$ as its set of leaves, and positive weights $\{p_i~|~i \in I\}$ with $\sum_I p_i = 1$. Each of these tree metrics [*dominates*]{} $d$, i.e., $dist_{T_i}(x,y) \ge d(x,y)$ for every $i$ and every $x,y
\in X$. On the other hand, for every $x,y \in X$, $$\sum_i p_i \cdot dist_{T_i}(x,y) \le O(\log n \cdot \log \log n
\cdot d(x,y)).$$

[*Bartal’s algorithmic paradigm*]{} is a general principle underlying the numerous algorithmic applications of this theorem: Given an algorithmic problem on input a graph or a general metric space $(X,d)$, find a collection of tree metrics $T_i$ and weights $p_i$ as in Theorem \[bartal\]. Select one of the trees at random, where $T_i$ is selected with probability $p_i$. Now solve the problem for input $T_i$. (This description assumes, and this is often the case, that the original optimization problem is $NP$-hard in general, but feasible for tree metrics.

There are two features of the proof that we’d like to mention:\
The trees $T_i$ are [*HST*]{}’s. In such trees, edge lengths decrease exponentially as you move from the root toward the leaves. They feature prominently in many recent developments in this area.\
The proof makes substantial use of [*sparse decompositions*]{} of graphs. Given a graph, one seeks a probability distribution on all partitions of the vertex set, so that (i) Parts have small diameters (ii) Adjacent vertices are very likely to reside in the same part. Such partitions have proved instrumental in the design of many algorithms. In fact, an important tool in Rao’s Theorem \[rao\_thm\] was an earlier result [@Kl:Pl:Rao] about the existence of very sparse partitions for the members of any minor-closed families family of graphs.

The mysterious [$l_1$]{} {#section_l1}
========================

-5mm

We know much less about metric embeddings into $l_1$, and the attempts to understand them give rise to many intriguing open problems. We start by defining the [*cut metric*]{} $d_S$ on $X$ where $S \subseteq X$, as follows: $d_S(x,y)
= 1$ if $x,y$ are separated by $S$ and is zero otherwise. A simple, but useful observation is that the collection of all $n$-point metrics in $l_1$ form a cone $\cal C$ whose extreme rays are the cut metrics. [^6] The book [@deza_lau] provides a coverage of this area.

We are now able to complete the proof of Theorem \[multicommodity\]. We retain the terminology of the discussion around that theorem. Linear programming duality yields the following alternative expression for the maximum $k$-commodity flow problem on $G=(V,E)$: $$\label{dual_multi} \max \phi = \min \frac{\sum_E d(i,j) \cdot
c_{ij}}{\sum_1^k D_j \cdot d(s_j,t_j)}.$$ Here the minimum is over all graphical metrics $d$ on $G$. Namely, you assign nonnegative [*lengths*]{} to $G$’s edges and $d$ is the induced shortest path metric on $G$’s vertices. Now let $d$ be the graphical metric that minimizes this expression. A slight adaptation of Bourgain’s embedding algorithm yields an $l_1$ metric $\rho$ so that $\rho(i,j) \le d(i,j)$ for all $i,j$ and $\rho(s_j,t_j) \ge \Omega(\frac{d(s_j,t_j)}{\log k})$ for all $j$. But the minimum of $\frac{\sum_E \rho(i,j) \cdot c_{ij}}{\sum_1^k
D_j \cdot \rho(s_j,t_j)}$ over $l_1$ metrics is attained for $\rho$ a cut metric, since cut metrics are the extreme rays of the cone of $l_1$ metrics $\cal C$. This minimum, over cut metrics is simply $\min \gamma(S)$, the sparsest cut value of the network. The conclusion follows.

The identification between $l_1$ metrics and the cut cone $\cal C$ makes it desirable to find an algorithm to solve linear optimization problems whose feasible set is this convex cone. Such an algorithm would solve at one fell swoop a host of interesting (and hard) problems such as max-cut, graph bisection and more. This hope is hard to realize, since the ellipsoid method (e.g. [@schrijver]) applies only to convex bodies for which we have efficient [*membership and separation oracles*]{}. For the convex cone $\cal C$, that would mean that we need to efficiently determine whether a given a real symmetric matrix $M$, represents the metric on $n$ points in $l_1$. Moreover, if not, we ought to find a hyperplane (in $n^2$ dimensions) that separates $M$ from $\cal C$. Unfortunately, these questions are $NP$-hard (e.g. [@deza_lau]). It becomes, therefore, interesting to [*approximate*]{} the cone $\cal C$. So, can we find another cone that is close to $\cal C$ and for which computationally efficient membership and separation oracles exist? There is a natural candidate for the job. We say that a matrix $M$ is in [*square*]{}-$l_2$, if there are points $x_i$ in $l_2$ such that $M_{ij} = \|x_i - x_j\|_2^2$. Let $\cal S$ be the collection of all all square-$l_2$ matrices which are also a metric (i.e. the entries in $M$ also satisfy the triangle inequality). It is not hard to see that $\cal C \subseteq \cal S$, but we ask:

What is the smallest $\alpha = \alpha(n)$, such that every $n
\times n$ matrix $M \in \cal S$ can be embedded in $l_1$ with distortion $\le \alpha$ ?

It is not hard to see that every finite $l_2$ metric embeds isometrically into $l_1$. But what about the opposite direction?

\[l1\_to\_l2\]Find $\max c_2(X)$ over all $(X,d)$ that are $n$-point metrics in $l_1$. As we saw above, for the $n=2^r$ vertices of the $r$-cube the answer is $\sqrt{r} = \sqrt{\log n}$. We suspect that this is the extreme case. No example is known where $c_2$ is asymptotically larger that $\sqrt{\log n}$.

Dimension reduction
-------------------

-5mm

Let us return to the applied aspect of this area. Even when a given metric space can be approximated well in some normed space, the [*dimension*]{} of the host space is quite significant. Data analysis and clustering in $l_2^N$ for large $N$ is by no means easy. In fact, practitioners in these areas often speak about the [*curse of dimensionality*]{} when they refer to this problem. In $l_2$ there is a basic result that answers this problem.

Every $n$-point metric in $l_2$ can be embedded into $l_2^k$ with distortion $< 1+\epsilon$ where $k \le O(\frac{\log
n}{\epsilon^2})$.

Here, again, the proof yields an efficient randomized algorithm. Namely, select a random $k$-dimensional subspace and project the points to it.

What is the appropriate analogue of this theorem for $l_1$ metrics?

What is the smallest $k = k(n,\epsilon)$ so that every $n$-point metric in $l_1$ can be embedded into $l_1^k$ with distortion $<
1+\epsilon$?

We know very little at the moment, namely $\Omega(\log n) \le k
\le O(n \log n)$ for constant $\epsilon >0$. The lower bound is trivial and the upper bound is from [@Sch_l1; @talagrand_l1]. Note that if the truth is at the lower bound, then this provides an affirmative answer to Open Problem \[l1\_to\_l2\].

Planar graphs and other minor-closed families
---------------------------------------------

-5mm

One of the most fascinating problems about $l_1$ metrics is:

Is there is an absolute constant $C > 0$ so that every metric of a planar graph embeds into $l_1$ with distortion $< C$?

Even more daringly, the same can be asked for every minor-closed family of graphs. Some initial success for smaller graph families has been achieved already [@Gup:New:Rab:Sin].

Large girth
-----------

-5mm

Is there an analogue of Theorem \[girth\_l2\] for embeddings into $l_1$?

How small can $c_1(G)$ be for a a graph $G$ of girth $g$ in which all vertices have degree $\ge 3$? Specifically, can $c_1(G)$ stay bounded as $g$ tends to $\infty$?

Ramsey-type theorems for metric spaces
======================================

-5mm

The philosophy of modern Ramsey Theory, (as developed e.g. in [@ramsey_book]) can be stated as follows: Large systems necessarily contain substantial “islands of order". Dvoretzky’s Theorem certainly falls into this circle of ideas. But what about the metric analogues?

What is the largest $f(\cdot,\cdot)$ so that every $n$-point metric $(X,d)$ has a subset $Y$ of cardinality $\ge f(n,t)$ with $c_2(Y) \le t$? (We mean, of course, the metric $d$ restricted to the set $Y$.)

For $t$ close to $1$, the answer is known, namely, $f(n,t) =
\Theta(\log n)$. For larger $t$ the behavior is known to be different [@Ba:Li:Me:Na].

[GNRS99]{}

N. Alon. Eigenvalues and expanders. , 6(2):83–96, 1986.

Y. Aumann and Y. Rabani. An ${O}(\log k)$ approximate min-cut max-flow theorem and approximation algorithm. , 27(1):291–301, 1998.

K. Ball. Markov chains, [R]{}iesz transforms and [L]{}ipschitz maps. , 2(2):137–172, 1992.

Yair Bartal. On approximating arbitrary metrices by tree metrics. In [*STOC ’98 (Dallas, TX)*]{}, 161–168. ACM, New York, 1998.

Yoav Benyamini and Joram Lindenstrauss. . American Mathematical Society, Providence, RI, 2000.

Y. Bartal, N. Linial, M. Mendel, and A. Naor. On metric [R]{}amsey-type phenomena. Manuscript.

Leonard M. Blumenthal. . Chelsea Publishing Co., New York, 1970.

J. Bourgain. On [L]{}ipschitz embedding of finite metric spaces in [H]{}ilbert space. , 52(1-2):46–52, 1985.

J. Bourgain. The metrical interpretation of superreflexivity in [B]{}anach spaces. , 56(2):222–230, 1986.

Jeff Cheeger. A lower bound for the smallest eigenvalue of the [L]{}aplacian. In [*Problems in analysis (Papers dedicated to Salomon Bochner, 1969)*]{}, 195–199. Princeton Univ. Press, Princeton, N. J., 1970.

Michel Marie Deza and Monique Laurent. . Springer-Verlag, Berlin, 1997.

J. Dunagan and S. Vempala. On [E]{}uclidean embeddings and bandwidth minimization. In [*Randomization, approximation, and combinatorial optimization (RANDOM-APPROX’99)*]{}, 229–240, Berlin, 1999. Springer-Verlag.

Aryeh Dvoretzky. Some results on convex bodies and [B]{}anach spaces. In [*Proc. Internat. Sympos. Linear Spaces (Jerusalem, 1960)*]{}, 123–160. Jerusalem Academic Press, Jerusalem, 1961.

P. Enflo. On the nonexistence of uniform homeomorphisms between ${L}\sb{p}$-spaces. , 8:103–105, 1969.

U. Feige. Approximating the bandwidth via volume respecting embeddings. , 60(3):510–539, 2000.

A. Gupta, I. Newman, Y. Rabinovich, and A. Sinclair. Cuts, trees and $l_1$ embeddings of graphs. In [*40th Annual IEEE Symposium on Foundations of Computer Science*]{}, 230–240, November 1999.

Ronald L. Graham, Bruce L. Rothschild, and Joel H. Spencer. . John Wiley & Sons Inc., New York, second edition, 1990.

P. Indyk. Algorithmic applications of low-distortion geometric embeddings. In [*42nd Annual IEEE Symposium on Foundations of Computer Science*]{}, 10–33, 2001.

W. B. Johnson and J. Lindenstrauss. Extensions of [L]{}ipschitz mappings into a [H]{}ilbert space. In [*Conference in modern analysis and probability (New Haven, Conn., 1982)*]{}, 189–206. Amer. Math. Soc., Providence, RI, 1984.

P. Klein, S. A. Plotkin, and S. Rao. Excluded minors, network decomposition, and multicommodity flow. In [*25th Annual ACM Symposium on Theory of Computing*]{}, 682–690, May 1993.

N. Linial, E. London, and Y. Rabinovich. The geometry of graphs and some of its algorithmic applications. , 15(2):215–245, 1995.

N. Linial and A. Magen. Least-distortion [E]{}uclidean embeddings of graphs: products of cycles and expanders. , 79(2):157–171, 2000.

N. Linial, A. Magen, and A. Naor. Girth and [E]{}uclidean distortion. To appear.

N. Linial and M. Saks. On the [E]{}uclidean distortion of complete binary trees. To appear.

J. Matou[š]{}ek. On embedding expanders into $l\sb p$ spaces. , 102:189–197, 1997.

J. Matou[š]{}ek. On embedding trees into uniformly convex [B]{}anach spaces. , 114:221–237, 1999.

J. Matou[š]{}ek. . Springer Verlag, New York, 2002. Graduate Texts in Mathematics 212.

V. D. Milman and G. Schechtman. . Springer-Verlag, Berlin, 1986.

I. Newman and Y. Rabinovich. A lower bound on the distortion of embedding planar metrics into [E]{}uclidean space. In [*Proceedings of the 18th annual symposium on Computational Geometry*]{}, 94–96. ACM, 2002.

S. Rao. Small distortion and volume preserving embeddings for planar and [E]{}uclidean metrics. In [*Proceedings of the 15th Annual Symposium on Computational Geometry*]{}, 300–306. ACM, 1999.

Y. Rabinovich and R. Raz. Lower bounds on the distortion of embedding finite metric spaces in graphs. , 19(1):79–94, 1998.

Gideon Schechtman. More on embedding subspaces of ${L}\sb p$ in $l\sp n\sb r$. , 61(2):159–169, 1987.

A. Schrijver. . Springer, Heidelberg, 2002.

Michel Talagrand. Embedding subspaces of ${L}\sb 1$ into $l\sp {N}\sb 1$. , 108(2):363–369, 1990.

\[lastpage\]

[^1]: School of Computer Science and Engineering, Hebrew University, Jerusalem 91904, Israel. E-mail:nati@cs.huji.ac.il

[^2]: Here and elsewhere, unless otherwise stated, $n = |X|$, the cardinality of the metric space in question.

[^3]: We freely interchange between a graph and its (shortest path) metric.

[^4]: This is not quite accurate. Given an $n$-point space $(X,d)$ and $\epsilon > 0$, the algorithm can determine $c_2(X,d)$ with relative error $<\epsilon$ in time polynomial in $n$ and $\frac{1}{\epsilon}$.

[^5]: $A$’s first eigenvalue is clearly $k$. This is the combinatorial analogue of Cheeger’s Theorem [@cheeger] about the spectrum of the Laplacian.

[^6]: For each $n$, the $n$-point metrics in $l_1$ form a cone $\cal C \rm_n$, but we suppress the index $n$.
