ICS Theory Group

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


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).