Department of Computer Science
 
Chair V

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

12.06.2015

Towards Better Inapproximability Bounds for TSP: A Challenge of Global Dependencies
Marek Karpinski
[Download PostScript] [Download PDF]

We present in this paper some of the recent techniques and methods for proving best up to now explicit approximation hardness bounds for metric symmetric and asymmetric Traveling Salesman Problem (TSP) as well as related problems of Shortest Superstring and Maximum Compression. We attempt to shed some light on the underlying paradigms and insights which lead to the recent improvements as well as some inherent obstacles for further progress on those problems.

Last Change: 06/12/15 at 10:17:32
 Deutsch 		University of Bonn -> Department of Computer Science -> Chair V