Institut für Informatik
 
Abteilung V

 
Universität Bonn -> Institut für Informatik -> Abteilung V
CS-APX-Reports 2013 Copyright 2013 Universität Bonn, Institut für Informatik, Abt. V
89143

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
 English
Universität Bonn -> Institut für Informatik -> Abteilung V