## CompSci 269S, Winter 2007: Theory Seminar

### Jan 26, 2007, in CS 243

# Approximation Algorithms for Embedding General Metrics Into
Trees

## Mihai Badoiu, Piotr Indyk, and Anastasios Sidiropoulos; appeared
in SODA 2007

## Presented by Kevin Wortman

Abstract:

We consider the problem of embedding general metrics into trees. We
give the first non-trivial approximation algorithm for
minimizing the
multiplicative distortion. Our algorithm produces an embedding with
distortion (c log n)^\sqrt(O( log delta)), where c is the
optimal
distortion, and delta is the spread of the metric (i.e. the
ratio of the
diameter over the minimum distance). We give an improved
O(1)-approximation algorithm for the case where the input is the
shortest path metric over an unweighted graph. Moreover, we show that
by composing our approximation algorithm for embedding general
metrics
into trees, with the approximation algorithm of [BCIS05] for
embedding
trees into the line, we obtain an improved approximation algorithm
for
embedding general metrics into the line.

We also provide almost tight bounds for the relation between
embedding
into trees and embedding into spanning subtrees. We show that for any
unweighted graph G, the ratio of the distortion required to embed G
into a spanning subtree, over the distortion of an optimal tree
embedding of G, is at most O(log n). We complement this bound by
exhibiting a family of graphs for which the ratio is
Omega(log n/ log log n).