  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^*$ of $K_n$ with the following property:
the proportion of Hamilton cycles of $K_n$ 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.
