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" [...]


  Do you need Payday Loans Missouri as soon as possible? What can cause long-term use of Canadian Viagra? In the network and other sources of information, there is no reliable data on the long-term use of Viagra and its negative effects on the body.