Projects per year
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 polynomialtime algorithm which has domination ratio 1n1/29. In other words, given a {0,1}edgeweighting 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 n1/29. Our analysis is based on a martingale approach. Previously, the best result in this direction was a polynomialtime algorithm with domination ratio 1/2o(1) for arbitrary edgeweights. We also prove a hardness result showing that, if the Exponential Time Hypothesis holds, there exists a constant C such that n1/29 cannot be replaced by exp((logn)C) in the result above.
Original language  English 

Pages (fromto)  427453 
Journal  Random Structures and Algorithms 
Volume  48 
Issue number  3 
Early online date  8 Oct 2015 
DOIs  
Publication status  Published  1 May 2016 
Keywords
 Algorithms
 Combinatorial dominance
 Travelling salesman problem
ASJC Scopus subject areas
 Computer Graphics and ComputerAided 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.Projects
 1 Finished

EdgeColourings and Hamilton Decompostitions of Graphs
Engineering & Physical Science Research Council
1/06/12 → 30/09/14
Project: Research Councils