[Colloquium] Talwar talk today 12:15 at TTI

[Meridel Trimble]

TOYOTA TECHNOLOGICAL INSTITUTE TALK 

Speaker: Kunal Talwar
Berkeley

Speaker’s 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