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


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


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


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.


  Do you need Payday Loans Missouri as soon as possible? The main advantage of Viagra Soft Tablets comparing with other products of this type is its faster on-set effect.