A tight bound on approximating arbitrary metrics by tree metrics.
In this paper, we show that any n point metric space can be embedded into a distribution over dominating tree metrics such that the expected stretch of any edge is O(log n). This improves upon the result of Bartal who gave a bound of O(log n log log n). Moreover, our result is existentially tight; there exist metric spaces where any tree embedding must have distortion (log n)-distortion. This problem lies at the heart of numerous approximation and online algorithms including ones for group Steiner tree, metric labeling, buy-at-bulk network design and metrical task system. Our result improves the performance guarantees for all of these problems.
INTRODUCTION
1.1 Metric approximations
The problem of approximating a given graph metric by a
"simpler" metric has been a subject of extensive research,
motivated from several di#erent perspectives. A particularly
simple metric of choice, also favored from the algorithmic
# Supported by NSF grants CCR-0105533 and CCR-
9820897.
# Supported in part by a DPST scholarship and NSF grant
CCR-0105533.
Supported by NSF grant CCR-0105533.
Permission to make digital or hard copies of all or part of this work for
personal or classroom use is granted without fee provided that copies are
not made or distributed for profit or commercial advantage and that copies
bear this notice and the full citation on the first page. To copy otherwise, to
republish, to post on servers or to redistribute to lists, requires prior specific
permission and/or a fee.
STOC'03, June 9-11, 2003, San Diego, California, USA.
ACM 1-58113-674-9/03/0006 .$5.00.
point of view, is a tree metric, i.e. a metric arising from
shortest path distance on a tree containing the given points.
Ideally we would like that distances in the tree metric are no
smaller than those in the original metric and we would like
to bound the distortion or the maximum increase. However,
there are simple graphs (e.g. the n-cycle) for which the
distortion must be # n) [41, 7, 25].
To circumvent this, Karp [30] considered approximating the
cycle by a probability distribution over paths, and showed
a simple distribution such that the expected length of each
edge is no more than twice its original length. This gave a
competitive ratio of 2 for the k-server problem (on a cycle)
that had motivated this approach. Alon, Karp, Peleg and
West [1] looked at approximating arbitrary graph metrics by
(a distribution over) spanning trees, and showed an upper
bound of 2 O( # log n log log n) on the distortion.
Bartal [7] formally defined probabilistic embeddings and improved
on the previous result by showing how to probabilistically
approximate metrics by tree metrics with distortion
O(log 2 n). Unlike the result of Alon et.al. [1], Bartal's trees
were not spanning trees of the original graph, and had additional
Steiner points. He however showed that this probabilistic
approximation leads to approximation algorithms for
several problems, as well as the first polylogarithmic competitive
ratios for a number of on-line problems. We should
note that the trees that Bartal used have a special structure
which he termed hierarchically well separated. This
meant that weights on successive levels of the tree di#ered
by a constant factor. This was important for several of his
applications.
Konjevod, Ravi and Salman [34] showed how Bartal's result
improves to O(log n) for planar graphs, and Charikar
et.al. [17] showed similar bounds for low dimensional normed
spaces. Inspired by ideas from Seymour's work on feed-back
arc set [45], Bartal [8] improved his earlier result to
O(log n log log n). This of course led to improved bounds on
the performance ratios of several applications. Bartal also
observed that any probabilistic embedding of an expander
graph into a tree has distortion at least #ast n).
In this paper, we show that an arbitrary metic space can be
approximated by a distribution over dominating tree metrics
with distortion O(log n), thus closing the gap between the
lower and the upper bounds. Our result is constructive and
we give a simple algorithm to sample a tree from this distri-
bution. Our trees are also heirarchically well separated, like
Bartal's. This gives improved approximation algorithms for
various problems including group Steiner tree [24], metric labeling
[19, 32], buy-at-bulk network design [4], and vehicle
routing [16]. We give a more comprehensive list in section 3.
1.2 Related Work
Divide and conquer methods have been used to provide
polylogarithmic-factor approximation algorithms for numerous
graph problems since the discovery of an O(log n) approximation
algorithm for finding a graph separator [36].
The algorithms proceeded by recursively dividing a problem
using the above approximation algorithm, and then using
the decomposition to find a solution. Typically, the
approximation factor was O(log 2 n): a logarithmic factor
came from the O(log n) separator approximation, another
O(log n) factor came from the recursion. Using this frame-
work, polynomial-time approximation algorithms for many
problems are given in [36], for example: crossing number,
VLSI layout, minimum feedback arc set, and search number

Independently, Seymour [45] gave an O(log n log log n) bound
on the integrality gap for a linear programming relaxation of
the feedback arc set problem (for which the above techniques
had given an O(log 2 n) bound). In doing so, he developed
a technique that balanced the approximation factor of his
separator based procedure against the cost of the recursion
to significantly improve the bounds.
Even et al.[20] introduced linear programming relaxations
for a number of problems and combined them with Sey-
mour's techniques to give O(log n log log n)-approximation
algorithms for many of the problems that previously had
O(log 2 n) approximation algorithms, e.g., linear arrange-
ment, embedding a graph in d-dimensional mesh, interval
graph completion, minimizing storage-time product, and (sub-
set) feedback sets in directed graphs.
Bartal's results [8] implied O(log n log log n)-approximations
for still more problems. Moreover, he used probabilistic
techniques so as to bound the expected stretch of each edge,
not just the average. This led to polylogarithmic competitive
ratio algorithms for a number of online problems
(against oblivious adversaries) such as metrical task system
[10]. Charikar et.al. [16, 17] showed how to derandomize
the approximation algorithms that follow from Bartal's embeddings

This work also follows the line of research on embeddings,
with low distortion, graphs into other "nice" metric spaces,
which have good structural properties, such as Euclidean
and #1 spaces [37, 26, 18, 43, 23].
The work of Bourgain [14] showed that any finite metric
on n nodes can be embedded into #2 with logarithmic distortion
with the number of dimensions exponential in n.
Linial, London, and Rabinovich [37] modified Bourgain's
result to apply for #1 metrics and to use O(log 2 n) dimen-
sions. Aumann and Rabani [3] and Linial, London and Rabinovich
[37] gave several applications, including a proof of
a logarithmic bound on max-flow min-cut gap for multi-commodity
flow problems. They also gave a lower bound
on the distortion of any embeddings of general graphs into
#1 . For more details, we point the reader to Chapter 15 in
Matousek [38].
Embeddings of special graphs have also been considered by
many researchers. Gupta et al. [26] considered embeddings
or series-parallel graphs and outerplanar graphs into #1 with
constant distortion; Chekuri et al. [18] show a constant-
distortion embedding for k-outerplanar graphs. For planar
graph, Rao [43] gave an O( # log n)-distortion embedding
into #2 , which matched the lower bound given by Newman
and Rabinovich [39].
Graph decomposition techniques for many interesting classes
of graphs have also been extensively studied. For example,
Klein, Plotkin, and Rao's [31] result provided a constant factor
approximation for graphs that exclude fixed sized minors
(which includes planar graphs). Similar results were given
by Charikar et al. [17] for geometric graphs.
1.3 Our techniques
The algorithm relies on techniques from the algorithm for
0-extension given by Calinescu, Karlo# and Rabani [15],
and improved by Fakcharoenphol, Harrelson, Rao and Talwar
[21]. The CKR procedure implies a randomized algorithm
that outputs clusters of diameter about # such that
the probability of an edge e being cut is (de/#) log n, where
de is the length of the edge e. The analysis can in fact be
improved to replace the log n by the logarithm of the ratio
of number of vertices within distance # of e to the no. of
vertices within distance #/2; i.e. the number of times the
size of a neighbourhood of e doubles between #/2 and #.
Our algorithm runs a CKR like procedure for diameters 2 i ,
. to get a decomposition of the graph (which
can then be converted to a tree). Since the total number of
doublings over all these levels is bounded by log n.
2. THE ALGORITHM
In this section, we outline the algorithm for probabilistically
embedding an n point metric into a tree, and show that the
expected distortion of any distance is O(log n). Like previous
algorithms, we first decompose the graph hierarchically
and then convert the resulting laminar family to a tree.
2.1 Preliminaries
We define some notation first. Let the input metric be (V, d).
We shall refer to the elements of V as vertices or points. We
shall refer to a pair of vertices (u, v) as an edge. Without
loss of generality, the smallest distance is strictly more than
1. Let # denote the diameter of the metric (V, d). Without
loss of generality,
A metric (V # , d # ) is said to dominate (V, d) if for all u, v # V ,
it is the case that d # (u, v) # d(u, v). We shall be looking for
tree metrics that dominate the given metric.
Let S be a family of metrics over V , and let D be a distribution
over S. We say that (S, D) #-probabilistically approximates
a metric (V, d) if every metric in S dominates d and
for every pair of vertices
We shall be interested in #-probabilistically approximating
an arbitrary metric (V, d) by a distribution over tree metrics.
For a parameter r, an r-cut decomposition of (V, d) is a partitioning
of V into clusters, each centered around a vertex
and having radius at most r. Thus each cluster will have
diameter at most 2r.
A hierarchical cut decomposition of (V, d) is a sequence of
nested cut decompositions D0 , D1 , . , D # such that
. D i.e. the trivial partition (that puts all
vertices in a single cluster).
. D i is a 2 i -cut decomposition, and a refinement of D i+1 .
Note that each cluster in D0 has radius at most 1 and hence
must be a singleton vertex.
2.2 Decompositions to trees
A hierarchical cut decomposition defines a laminar family 1 ,
and naturally corresponds to a rooted tree as follows. Each
set in the laminar family is a node in the tree and the children
of a node corresponding to a set S are the nodes corresponding
to maximal subsets of S in the family. Thus the
node corresponding to V is the root and the singletons are
the leaves. Also note that the children of a set in D i+1 are
sets in D i . (See figure 1).
We define a distance function on this tree as follows. The
links from a node S in D i to each of its children in the tree
have length equal to the 2 i (which is an upper bound on the
radius of S). This induces a distance function d T (-) on V
where d T (u, v) is equal to the length of the shortest path
distance in T from node {u} to node {v}. Given the length
function, it is easy to see that d T (u, v) # d(u, v) for all u
and v.
We shall also like to place upper bounds on d T (u, v). We
say an edge (u, v) is at level i if u and v are first separated in
the decomposition D i . Note that if (u, v) is at level i, then
2.3 Decomposing the graph
We shall describe a random process to define a hierarchical
cut decomposition of (V, d), such that the probability that
an edge (u, v) is at level i decreases geometrically with i.
We first pick a random permutation # of {v1 , v2 , . , vn},
which will be used throughout the process. We also pick a
# uniformly at random in the interval [1, 2]. For each i, we
compute D i from D i+1 as follows. First set # i to be 2 i-1 #.
Let S be a cluster in D i+1 . We assign a vertex u # S to the
first (according to #) vertex v # V closer than # i to u. Each
child cluster of S in D i then consists of the set of vertices in
S assigned to a single center v. Note that the center v itself
need not be in S. Thus one center v may correspond to more
than one cluster, each inside a di#erent level (i
1 Recall that a laminar family F # 2 V is a family of subsets
of V such that for any A, B # F , it is the case that A # B
or B # A or A #
(2)

Figure

2: A possible hierarchical cut decomposition
output by the algorithm. The varying thicknesses
indicate cuts at di#erent levels.
(see for example, the center #(8) in figure 2). Note that
since the radius of each cluster is at most 2 i and
thus we indeed get a 2 i -cut decomposition. More formally,
Algorithm Partition (V, d)
1. Choose a random permutation # of v1 , v2 , . , vn .
2. Choose # uniformly at random in [1, 2].
3. D # {V }; i # - 1.
4. while D i+1 has non-singleton clusters do
4.1
4.2 For do
4.2.1 For every cluster S in D i+1 .
4.2.1.1 Create a new cluster consisting of all unassigned
vertices in S closer than # i to #(l).
4.3
It is easy to see that the algorithm can be implemented in
time O(n 3 ). A more careful implementation can actually
be made to run in time O(n 2 ) (i.e. linear in the size of the
input).
We now fix an arbitrary edge (u, v), and show that the expected
value of d T (u, v) is bounded by O(log n) - d(u, v). We
shall make no attempts to optimize the constants in this
analysis. From the discussion above, it follows that
E[d T
Pr[(u, v) is at level i] - 2 i+2
(1)
We shall show that the right hand side of this equation is
bounded by O(log n) - d(u, v).
If vertices u and v are in separate clusters in D i , we say that
separates (u, v). Now note that (u, v) is at level i if
(a) D i separates (u, v).
(b) D j does not separate (u, v) for any j > i.
Dia(S1)/2 Dia(S2)/2 .

Figure

1: Converting a laminar family into a tree. Note that the values we put on the links ensure that the
embedding is an expansion.
then u and v cannot be in the
same cluster in D i+1 , i.e., D i+1 separates (u, v). From (b)
above, (u, v) cannot be at level i. Let j # be the smallest i
such that d(u, v) # 2 i+2 . Thus Pr[(u, v) is at level
any i < j#. For we shall bound the probability that
(u, v) is at level i.
From (a) and (b) above, for any i # j # ,
Pr[(u, v) is at level i]
separates (u, v) | D i separates (u, v)]
For any j # j #, let K u
j be the set of vertices in V closer
than 2 j to vertex u, and let k u
|. We define K v
similarly. For j < j # , we let k u
Now consider the clustering step at level i # j#. In each
iteration, all unassigned vertices v such that d(v, #(l)) # i
assign themselves to #(l). For some initial iterations of this
procedure, both u and v remain unassigned. Then at some
step l, at least one of u and v gets assigned to the center #(l).
We say that center #(l) settles the edge (u, v) at level i if it is
the first center to which at least one of u and v get assigned.
Note that exactly one center settles any edge (u, v) at any
particular level. Further, we say that center #(l) cuts the
at level i if it settles e at this level, but exactly
one of u and v is assigned to #(l) at level i. Clearly, D i
separates (u, v) i# some center w cuts it at this level. Hence
cuts (u, v) at level i].
We say that center w cuts u out of (u, v) at level i if w
cuts (u, v) at this level and u is assigned to w (and v is not
assigned to w) at this level. For each center w, we shall
bound the probability that w cuts u out of (u, v) at level
i. Let us arrange the centers in K u
in increasing order of
2 Though the notation does not explicitly suggest so, these
k u
, etc. are then defined with respect to the edge (u, v).
distance from u, say w1 , w2 , . , wk u
. For a center ws to cut
(u, v) such that only u is assigned to ws , it must be the case
that
(a) d(u, ws) # i .
(b)
(c) ws settles e.
Thus # i must lie in [d(u, ws), d(v, ws )] (see figure 3). By
triangle inequality, d(v, ws) # d(v, u)
the interval [d(u, ws), d(v, ws )] is of length at most d(u, v).
distributed uniformly in [2 i-1 , 2 i ], the probability
that # i falls in the bad interval is at most (d(u, v)/2 i-1 ).
Moreover for such a value of # i , any of w1 , w2 , . , ws can
settle (u, v) at level i and hence the first amongst these in
the permutation # will. Since # is a random permutation,
the probability that ws is the one to settle (u, v) at level i
is at most 1/s.
At this point, it is then easy to see that the probability that
separates (u, v) is at most
k u
s
s
Thus each i contributes at most O(log n) to the expected
value of d T (u, v) (equation 1) and hence the expected length
is bounded by O(log n log #).
We however promised to show an improved bound of O(log n).
We shall do so by observing that the total number of centers
over all # levels is n. A more careful analysis of the above
procedure will yield the result.
Let us first consider some 4. Since the radius of the
cluster at level i is at least 2 i-1 , centers very close to both u
center w can cut (u,v)
Centers that can settle
(u,v) for this value of bi

Figure

3: Bounding the probability of an edge being cut. Each shaded rectangle represents a center; arrow
marks indicate distances from u and v. Width of each shaded rectangle is at most d(u, v)
and v can never cut the edge (u, v). More precisely, for any
w in K u
i-2 , if u is assigned to w, it must be the case that v
gets assigned to w also, because d(v, w) # d(v, u)+d(u, w) #
no center in
can ever cut u out of (u, v). This implies
that the probability that u gets cut out of edge e is in fact
bounded by
k u
s=k u
Since (u, v) can be cut when either u or v is cut out by
some vertex, the overall probability that D i separates (u, v)
is then at most (d(u, v)/2 i-1 )-[Hk u
For we just bound this probability
by (d(u, v)/2 i-1
The expected value of d T (u, v) is therefore.
E[d T (u, v)]
Pr[(u, v) is at level i] - 2 i+2
(Hk u
+Hk u
+Hk u
The third to last inequality follows because alternate terms
of the summation # i (Hk u
telescope. Thus, we
have shown that for any edge (u, v), the expected value of
d T (u, v) is O(log n) - d(u, v). Hence,
Theorem 1. The distribution over tree metrics resulting
from our algorithm O(log n)-probabilistically approximates
the metric d.
We note that by choosing a slightly di#erent distribution
for #, we can ensure that for any x (not just in [1, 2]), the
probability that there is some # i in [x, x
)dx.
This then makes the analysis simpler 3 , and we do not have
to deal with the corner cases above. We omit the details
from this extended abstract.
2.4 HSTs
A tree T is said to be k-hierarchically well separated if on
any root to leaf path the edge lengths decrease by a factor
of k in each step. Bartal [7, 8] constructed distributions
over trees which were hierarchically well separated,
and such trees are more conducive to design of divide-and-
conquer type algorithms. The fact that the trees are well
separated has been used in applications such as metrical
task system[10] and metric labeling [32]. We note that the
trees we construct are 2-HSTs. Bartal [8] also observed that
a 2-HST can be converted to a k-HST with distortion O(k),
later improved to O(k/ log This combined with our
result implies a probabilistic embedding into k-HSTs with
distortion O(k log n/ log k). In fact, a slight modification of
our technique (details omitted) can be used to directly get
k-HSTs for any k, with distortion O( k log n
log k
). This can be
useful in some applications, e.g. min-sum k-clustering.
2.5 Derandomization
The problem of probabilistic approximation by tree metrics
asks for a distribution over tree metrics such that the expected
stretch of each edge is small. A dual problem is find
3 But somewhat less intuitive.
a single tree such that the (weighted) average stretch of the
edges is small. More precisely, given weights wuv on edges,
find a tree metric d T such that for all u, v in V ,
. d T (u, v) # d(u, v).
. # u,v#V wuv - d T (u, v) # u,v#V wuv - d(u, v).
Charikar et.al.[17] showed that solving this problem is enough
for most applications, and moreover can give deterministic
algorithms. The algorithm of the previous section clearly
gives a randomized algorithm that solves the dual problem
n). We were however looking for deterministic
algorithms. The above algorithm can actually be derandomized
by the method of conditional expectation as follows.
The algorithm described above tosses coins to choose #
[1, 2] and a permutation #. Since there are only n 2 distinct
distances, there are only that many values of # that mat-
ter. For each of them, suppose we can compute exactly the
expected cost of the tree when # is chosen randomly. Then
we can find one for which this expectation is smaller than
the average (which is O(log n)). We then choose the permutation
# one vertex at a time. To use the method of
conditional expectation again, we need to be able to com-
pute, having fixed # and a prefix of the permutation #, the
expected cost of the tree, where the expectation is taken
over random choices of the rest of #. Assuming we could do
this in polynomial time, we simply try all possible choices
for the next vertex in the permutation, and pick the one
which maximizes the conditional expectation.
It remains to show how to compute the conditional expec-
tations. Given # and some (possibly empty) prefix of #,
each edge, at each level is either settled or not. In the former
case, the cost at that level is already determined. In
the latter case, we know the set of vertices that can settle
the edge and the set of vertices that can cut the edge at a
particular level. Thus we can compute exactly the expected
cost of a particular edge at a particular level. By linearity
of expectation then, we can compute the total expected
cost. Hence we can solve the dual problem in deterministic
polynomial time. In fact, the computation above can
be simplified, replacing the exact value of the expected cost
above by the upper bounds used in the analysis (and thus
using the method of pessimistic estimators [42]).
3. APPLICATIONS
Many problems are easy on trees. The partitioning algorithm
we give produces a tree such that the expected stretch
of each edge is at most O(log n). By using our result, the
approximation ratios of various problems can be improved.
The following is a list of some our favorite applications.
The metric labeling problem : The previous result of Kleinberg
and Tardos [32] gives an O(log k log log k)-approximation
algorithm based on a constant factor approximation for the
case that the terminal metric is an HST. Our result improves
this to O(log n).
We also note that Archer, Talwar and Tardos [2] show that
the earthmover linear program of Chekuri et.al.[19] is integral
when the input graph is a tree. Using this result, the approximation
ratio can be improved to O(min(log k, log n)).
Buy-at-bulk network design : Awerbuch and Azar [4] give a
O(1)-approximation algorithm on trees. Thus, we can get
an O(log n)-approximation algorithm.
Minimum cost communication network problem : This problem
[28, 40, 46] is essentially the dual problem defined in
section 2.5 and hence we get an O(log n) approximation.
The group Steiner tree problem : Garg, Konjevod, and Ravi [24]
give an O(log k log n)-approximation algorithm for trees; thus,
we obtain an O(log 2 n log k)-approximation algorithm, improving
on the O(# log n log by Bartal and Mendel [12],
log log log n, log # log log #}).
Metrical Task system : Improving on the result of Bartal,
Blum, Burch and Tomkins [10], Fiat and Mendel [22] gave
an O(log n log log n)-competitive algorithms on HSTs. Bartal
and Mendel's [12] multiembedding result thus gives an
O(# log n log log n)-competitive ratio, where # is as defined
above. Our result improves this to an O(log 2 n log log n)-
competitive ratio against oblivious adversaries.
The result also improves the performance guarantees of several
other problems such as vehicle routing [16], min sum
clustering [11, 9], covering steiner tree [33], hierarchical placement
[35], topology aggregation [6, 44], mirror placement [29],
distributed K-server [13], distributed queueing [27] and mobile
user [5]. We refer the reader to to [8] and [17] for more
detailed descriptions of these problems.
4.

ACKNOWLEDGEMENTS

We would like to thank Yair Bartal for helpful comments on
a previous draft of the paper, and for pointing us to several
of the aforementioned applications.
5.



--R

A graph-theoretic game and its application to the k-server problem
Personal Communication
An O(log theorem and approximation algorithm

Concurrent online tracking of mobile users.
Topology aggregation for directed graphs.
Probabilistic approximations of metric spaces and its algorithmic applications.
On approximating arbitrary metrics by tree metrics.
A constant factor approximation for min sum clustering on HSTs.
A polylog(n)-competitive algorithm for metrical task systems
Approximating min-sum k-clustering in metric spaces

The distributed k-server problem-a competitive distributed translator for k-server algorithms
On lipschitz embeddings of finite metric spaces in hilbert space.

Rounding via trees: deterministic approximation algorithms for group Steiner trees and k-median
Approximating a finite metric by a small number of tree metrics.
Embedding k-outerplanar graphs into #1
Approximation algorithms for the metric labeling problem via a new linear programming formulation.

An improved approximation for the 0-extension problem
Better algorithms for unfair metrical task systems and applications.
Approximating the bandwidth via Volume
A polylogarithmic approximation algorithm for the group steiner tree problem.
Steiner points in tree metrics don't (really) help.
Cuts, trees and l 1-embeddings of graphs
Competitive concurrent distributed queueing.
Optimum communication spanning trees.
On the placement of internet instrumentation.

Excluded minors
Approximation algorithms for classification problems with pairwise relationships: Metric labeling and markov random fields.
An approximation algorithm for the covering steiner problem.
On approximating planar metrics by tree metrics.
Placement algorithms for hierarchical cooperative caching.
An approximate max-flow min-cut theorem for uniform multicommodity flow problems with application to approximation algorithms
The geometry of graphs and some of its algorithmic applications.
Lectures on discrete geometry.
A lower bound on the distortion of embedding planar metrics into euclidean space.
Deterministic polylog approximation for minimum communication spanning trees.
Lower bounds on the distortion of embedding finite metric spaces in graphs.
Probabilistic construction of deterministic algorithms: Approximating packing integer programs.
Small distortion and Volume

Packing directed circuits fractionally.
A polynomial time approximation scheme for mimimum routing cost spanning trees.
--TR
Probabilistic construction of deterministic algorithms: approximating packing integer programs
Concurrent online tracking of mobile users
Excluded minors, network decomposition, and multicommodity flow
A Graph-Theoretic Game and its Application to the $k$-Server Problem
A polylog(<italic>n</italic>)-competitive algorithm for metrical task systems
An <i>O</i>(log <i>k</i>) Approximate Min-Cut Max-Flow Theorem and Approximation Algorithm
Approximating the bandwidth via volume respecting embeddings (extended abstract)
Rounding via trees
On approximating arbitrary metrices by tree metrics
Small distortion and volume preserving embeddings for planar and Euclidean metrics
A polynomial time approximation scheme for minimum routing cost spanning trees
Placement algorithms for hierarchical cooperative caching
Better algorithms for unfair metrical task systems and applications
An approximation algorithm for the covering Steiner problem
Approximation algorithms for the 0-extension problem
Approximation algorithms for the metric labeling problem via a new linear programming formulation
Steiner points in tree metrics don''t (really) help
Approximating min-sum <italic>k</italic>-clustering in metric spaces
Competitive concurrent distributed queuing
A lower bound on the distortion of embedding planar metrics into Euclidean space
Lectures on Discrete Geometry
Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications
An improved approximation algorithm for the 0-extension problem
Multi-embedding and path approximation of metric spaces
Embedding <i>k</i>-outerplanar graphs into <i>MYAMPERSANDell;</i><inf>1</inf>
Deterministic Polylog Approximation for Minimum Communication Spanning Trees
Divide-and-conquer approximation algorithms via spreading metrics
Buy-at-bulk network design
Approximating a Finite Metric by a Small Number of Tree Metrics
Cuts, Trees and -Embeddings of Graphs
Approximation Algorithms for Classification Problems with Pairwise Relationships
Topology Aggregation for Directed Graph
Probabilistic approximation of metric spaces and its algorithmic applications
Approximate classification via earthmover metrics

--CTR
Manthey, Non-approximability of weighted multiple sequence alignment for arbitrary metrics, Information Processing Letters, v.95 n.3, p.389-395, August 2005
Matthias Englert , Harald Rcke , Matthias Westermann, Reordering buffers for general metric spaces, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA
Yair Bartal , Bla Bollobs , Manor Mendel, Ramsey-type theorems for metric spaces with applications to online problems, Journal of Computer and System Sciences, v.72 n.5, p.890-921, August 2006
Anupam Gupta , Amit Kumar , Martin Pal , Tim Roughgarden, Approximation via cost sharing: Simpler and better approximation algorithms for network design, Journal of the ACM (JACM), v.54 n.3, p.11-es, June 2007
tree metrics;embeddings;metrics