From: Venkatesan Guruswami (venkat@cs.washington.edu)
Date: Mon Feb 09 2004 - 20:00:00 PST
NOTE: I've scheduled this at the same time as the student seminar 590zz
since I wasn't sure two seminars in a day was the way to go. I checked with
couple of students whether this intrusion was acceptable and no objections
were raised. But, if I hear otherwise in response to this email, we can have
this seminar at 3:30PM. I've the room booked through to 4:30pm.
(Please let me know by tomorrow afternoon if you would like the time
changed.)
*************
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 : Mon Feb 09 2004 - 20:25:38 PST