New Approximation Algorithms for Traveling Salesman Problem

We design improved approximation algorithms for the following problem: given a graph G=(V,E), find the shortest tour that visits every vertex at least once. This problem is known as the graphic TSP. It 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 Christofides.

Similar to Christofides, our algorithm finds a spanning tree whose cost is upper bounded by the optimum, then it adds the minimum cost perfect matching on the odd degree vertices of that tree. The main difference is in the selection of the spanning tree. Except in certain cases where the solution of LP is nearly integral, we select the spanning tree randomly by sampling from a maximum entropy distribution defined by the linear programming relaxation.

Despite the simplicity of the algorithm, the analysis builds on a variety of ideas such as properties of strongly Rayleigh measures from probability theory, graph theoretical results on the structure of near minimum cuts, and the integrality of the T-join polytope. Also, as a byproduct of our result, we show new properties of random spanning trees as well as new properties of the near minimum cuts of any graph, which may be of independent interest.

发言人详细信息

Shayan Oveis Gharan is currently finishing his PhD at Stanford University under the supervision of Amin Saberi.
Prior to Stanford, Shayan received a BA in computer engineering from Sharif University of Technology. His research interests
include Approximation Algorithms, Spectral Algorithms, Online Algorithms and Applied Probability.
He is a recipient of the best paper award at SODA 2010 and FOCS 2011 for his works on the Traveling Salesman Problem.

日期：
演讲者：
Shayan Oveis Gharan
所属机构：
Stanford