**Tuesday, 15:15 - 15:40 h, Room: H 3010**

**Mohit Singh**

A randomized rounding approach to the traveling salesman problem

**Coauthors: Shayan Oveis Gharan, Amin Saberi**

**Abstract:**

For some positive constant *ε*, we give a *(3⁄2-ε)*-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 Christofides for this special case.

Similar to Christofides, our algorithm finds a spanning tree whose cost is upper bounded by the optimum, 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 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.

Talk 1 of the invited session Tue.3.H 3010

**"Travelling salesman problem II"** [...]

Cluster 1

**"Approximation & online algorithms"** [...]