From: Venkatesan Guruswami (venkat@cs.washington.edu)
Date: Wed Feb 11 2004 - 08:56:50 PST
Today, in place of 590zz, we have:
*************
Special CSE Theory Seminar
TIME: Wednesday, Feb 11, 2:30-3:20PM
PLACE: CSE 403
SPEAKER: Kunal Talwar
University of California, Berkeley
TITLE: Approximating arbitrary metrics by tree metrics
OR
Divide and Conquer type approximation algorithms
ABSTRACT:
Given a metric we consider the problem of approximating it by a
distribution over tree metrics. Since several problems, such as group
steiner tree, are easier on trees, this has applications to approximation
algorithms for several such problems. Bartal(1996) showed an upper bound
of O(log^2 n) (later improved to O(logn loglog n)) for the distortion of
such an embedding, and a lower bound of log n is known for expander
graphs. We close this gap by showing a simple algorithm that achieves
O(log n) distortion.
Our techniques apply more broadly to divide and conquer type approximation
algorithms for various problems (e.g. minimum linear arrangement). Our
decomposition techniques have also found other applications to metric
embeddings.
(Joint work with Jittat Fakcharoenphol and Satish Rao)
_______________________________________________
Theory-talks mailing list
Theory-talks@cs.washington.edu
http://mailman.cs.washington.edu/mailman/listinfo/theory-talks
_______________________________________________
Theory-group mailing list
Theory-group@cs.washington.edu
http://mailman.cs.washington.edu/mailman/listinfo/theory-group
This archive was generated by hypermail 2.1.6 : Wed Feb 11 2004 - 08:57:43 PST