2014/01/20 by Daniela Kühn, Kühn, Daniela, Deryk Osthus +3
Computer Science · Mathematics · #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #cs.DS #math.CO
paper · pdf · doi:10.48550/arxiv.1401.4931
29 pages (final version to appear in Random Structures and Algorithms)
arxiv created 2015/05/26 · arxiv updated 2015/05/27
We present an approximation algorithm for \0,1\-instances of the travelling salesman problem which performs well with respect to combinatorial dominance. More precisely, we give a polynomial-time algorithm which has domination ratio 1-n-1/29. In other words, given a \0,1\-edge-weighting of the complete graph Kn on n vertices, our algorithm outputs a Hamilton cycle H^* of Kn with the following property: the proportion of Hamilton cycles of Kn whose weight is smaller than that of H^* is at most n-1/29. Our analysis is based on a martingale approach. Previously, the best result in this direction was a polynomial-time algorithm with domination ratio 1/2-o(1) for arbitrary edge-weights. We also prove a hardness result showing that, if the Exponential Time Hypothesis holds, there exists a constant C such that n-1/29 cannot be replaced by exp(-(log n)C) in the result above.