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


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.


Talk 3 of the invited session Tue.3.H 3010
"Travelling salesman problem II" [...]
Cluster 1
"Approximation & online algorithms" [...]


  cash advance . The main active actual substance of Levitra Professional online - Vardenafil does not affect the seminal fluid and is not addictive.