[Colloquium] Kunal Talwar talk - tomorrow 12:15 at TTI
Meridel Trimble
mtrimble at tti-c.org
Wed Apr 7 13:06:16 CDT 2004
TOYOTA TECHNOLOGICAL INSTITUTE TALK
Speaker: Kunal Talwar
Berkeley
Speakers homepage: Speaker 's Homepage: http://www.cs.berkeley.edu/~kunal/
Thursday, April 8th 2004
Toyota Technological Institute - Chicago, 12:15 p.m.
Title: Approximating metrics by simpler metrics: Why and how?
Abstract:
The traveling salesman problem is NP-hard, as are several other optimization
problems such as group steiner tree and k-server. On the other hand, many such
problems are easy to solve when the underlying graph is simple, say a tree. A
natural approach to get approximately optimal solutions for the above problems
is to approximate the shortest path metric on the input graph by a simpler
metric and solve the problem on the resulting instance.
We show how to approximate any graph metric by a distribution over trees, such
that internode distances are preserved up to a logarithmic factor (in
expectation). This settles a long open question and gives simpler and improved
approximation algorithms for several problems. We also show how our techniques
lead to a quasi-polynomial approximation scheme for the traveling salesman
problem on low-dimensional metrics.
If you have questions, or would like to meet the speaker, please contact Meridel
at 4-9873 or mtrimble at tti-c.org
For information on future TTI-C talks or events, please go to the TTI-C Events
page: http://www.tti-c.org/events.shtml
More information about the Colloquium
mailing list