Paper Info
Title
A Randomized Rounding Approach to the Traveling Salesman Problem
Abstract
For some positive constant \eps_0, we give a (3/2-\eps_0)-approximation algorithm for the following problem: given a graph G_0=(V,E_0), 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_0. The result improves on the 3/2-approximation algorithm due to Christofides [C76] for this special case. Similar to Christofides, our algorithm finds a spanning tree whose cost is upper bounded by the optimum, then it finds the minimum cost Eulerian augmentation (or T-join) 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 from polyhedral theory. Also, as a byproduct of our result, we show new properties of the near minimum cuts of any graph, which may be of independent interest.
Year
DOI
Venue
2011
10.1109/FOCS.2011.80
Foundations of Computer Science
Keywords
DocType
ISSN
graph theory,linear programming,probability,travelling salesman problems,Eulerian augmentation,Rayleigh measurement,approximation algorithm,graph theory,linear programming,polyhedral theory,positive constant,probability theory,randomized rounding approach,spanning tree,traveling salesman problem,Approximation Algorithms,Random Spanning Trees,Randomized Rounding,Traveling Salesman Problem
Conference
0272-5428
ISBN
Citations 
PageRank 
978-1-4577-1843-4
56
2.27
References 
Authors
20
3
Name
Order
Citations
PageRank
Shayan Oveis Gharan132326.63
Amin Saberi22824224.27
mohit singh351538.42