A domination algorithm for $\{0,1\}$-instances of the travelling salesman problem

Abstract

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 $K_n$ on $n$ vertices, our algorithm outputs a Hamilton cycle $H^{\ast }$ of $K_n$ with the following property: the proportion of Hamilton cycles of $K_n$ whose weight is smaller than that of $H^{\ast }$ 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.

arXiv comment29 pages (final version to appear in Random Structures and Algorithms)