Department of Computer Science
 
Chair V

 
University of Bonn -> Department of Computer Science -> Chair V
CS-Reports 2013 Copyright 2013 University of Bonn, Department of Computer Science, Abt. V
85335

26.03.2013

New Inapproximability Bounds for TSP
Marek Karpinski, Michael Lampis and Richard Schmied
[Download PostScript] [Download PDF]

In this paper, we study the approximability of the metric Traveling Salesman Problem, one of the most widely studied problems in combinatorial optimization. Currently, the best known hardness of approximation bounds are 185/184 for the symmetric case (due to Lampis) and 117/116 for the asymmetric case (due to Papadimitriou and Vempala). We present here two new reductions which improve these bounds to 123/122 and 75/74, respectively. One of our main tools, which may be of independent interest, is a new construction of a bounded degree wheel amplifier used in the proof of our results.

Last Change: 11/05/14 at 11:04:31
 Deutsch
University of Bonn -> Department of Computer Science -> Chair V