## Invited Session Tue.3.H 3010

#### Tuesday, 15:15 - 16:45 h, Room: H 3010

**Cluster 1: Approximation & online algorithms** [...]

### Travelling salesman problem II

**Chair: Sylvia Boyd and David Shmoys**

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

**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.

**Tuesday, 15:45 - 16:10 h, Room: H 3010, Talk 2**

**Tobias Mömke**

Approximationg graphic TSP by matchings

**Coauthor: Ola Svensson**

**Abstract:**

We present a framework for approximating the metric TSP based on a novel use of matchings. Traditionally, matchings have been used to add edges in order to make a given graph Eulerian, whereas our approach also allows for the removal of certain edges leading to a decreased cost. For the TSP on graphic metrics (graph-TSP), the approach yields a 1.461-approximation algorithm with respect to the Held-Karp lower bound. For graph-TSP restricted to a class of graphs that contains degree three bounded and claw-free graphs, we show that the integrality gap of the Held-Karp relaxation matches the conjectured ratio 4/3.

**Tuesday, 16:15 - 16:40 h, Room: H 3010, Talk 3**

**Marcin Mucha**

13/9-approximation for graphic TSP

**Abstract:**

The Travelling Salesman Problem (TSP) is one the most fundamental and most studied problems in approximation algorithms.

For more than 30 years, the best algorithm known for general metrics has been Christofides's algorithm with approximation factor of *3⁄2*,

even though the so-called Held-Karp LP relaxation of the problem is conjectured to have the integrality gap of only *4⁄3*.

In the so-called *graphic* version of TSP we assume that *(V,d)* is a shortest path metric of an unweighted, undirected graph. The reason why this special case is interesting is that it seems to include the difficult inputs of TSP. Not only is it APX-hard, but also the standard examples showing that the Held-Karp relaxation has a gap of at least *4⁄3* are in fact graphic.

Very recently, significant progress has been made for the graphic TSP, first by Oveis Gharan et al.,

and then by Mömke and Svensson. In this paper, we provide an improved analysis of the approach used by the latter yielding

a bound of *13⁄9* on the approximation factor. We also provide improved bounds for the related graphic TSP path problem.