A Randomized Rounding Approach for Symmetric TSP

Show full item record

Please use this identifier to cite or link to this item: http://hdl.handle.net/1853/42028

Title: A Randomized Rounding Approach for Symmetric TSP
Author: Singh, Mohit
Abstract: We show a (3/2-epsilon)-approximation algorithm for the graphical traveling salesman problem where the goal is to find a shortest tour in an unweighted graph G. 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 Christofides for the case of graphical TSP. Similar to Christofides, our algorithm first finds a spanning tree whose cost is upper-bounded by the optimum and then it finds the minimum cost Eulerian augmentation 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 strong 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. This is joint work with Shayan Oveis Gharan and Amin Saberi.
Description: Presented on November 11, 2011 in Klaus 1116 Runtime: 54:36 minutes
Type: Lecture
URI: http://hdl.handle.net/1853/42028
Date: 2011-11-11
Contributor: Georgia Institute of Technology. Algorithms, Randomness and Complexity Center
McGill University
Georgia Institute of Technology. School of Mathematics
Georgia Institute of Technology. School of Computer Science
Relation: ARC Theory Day
Publisher: Georgia Institute of Technology
Subject: Traveling salesman problem

All materials in SMARTech are protected under U.S. Copyright Law and all rights are reserved, unless otherwise specifically indicated on or in the materials.

Files in this item

Files Size Format View Description
msingh.mp4 147.6Mb MPEG-4 video View/ Open Download Video
msingh_streaming.html 922bytes HTML View/ Open Streaming Video

This item appears in the following Collection(s)

Show full item record