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

Daniela Kühn, Deryk Osthus, Viresh Patel*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

2 Citations (Scopus)
169 Downloads (Pure)

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 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(-(logn)C) in the result above.

Original languageEnglish
Pages (from-to)427-453
JournalRandom Structures and Algorithms
Volume48
Issue number3
Early online date8 Oct 2015
DOIs
Publication statusPublished - 1 May 2016

Keywords

  • Algorithms
  • Combinatorial dominance
  • Travelling salesman problem

ASJC Scopus subject areas

  • Computer Graphics and Computer-Aided Design
  • Software
  • Mathematics(all)
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'A domination algorithm for {0,1}-instances of the travelling salesman problem'. Together they form a unique fingerprint.

Cite this