Institut für Informatik
 
Abteilung V

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

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