A Randomized Rounding Approach to the Traveling Salesman Problem
Speaker: Amin Saberi , Stanford U.
Date: May 3 2011
Time: 3:45PM to 4:15PM
Location: 32-155
Host: Scott Aaronson, CSAIL, MIT
Contact: Be Blackburn , 3-6098, be@csail.mit.edu
Relevant URL: For some positive constant c, we give a 3/2-c approximation algorithm
for the following problem: given a graph G(V; E), find the shortest
tour that visits every vertex at least once. This is a special case of
the metric traveling salesman problem when the underlying metric is
defined by shortest path distances in G. The result improves on the
3/2 -approximation algorithm due to Christodes.
Joint work with M. Singh and S. Oveis Gharan
See other events that are part of Theory Colloquium 2010/2011
See other events happening in May 2011
