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
89147

01.05.2013

Improved Inapproximability Results for the Shortest Superstring and the Bounded Metric TSP
Marek Karpinski and Richard Schmied
[Download PostScript] [Download PDF]

We present a new method for proving explicit approximation lower bounds for the Shortest Superstring problem, the Maximum Compression problem, Maximum Asymmetric TSP problem, the (1,2)–ATSP problem, the (1,2)–TSP problem, the (1,4)–ATSP problem and the (1,4)–TSP problem improving on the best up to now known approximation lower bounds for those problems.

Last Change: 11/05/14 at 11:03:33
 English
Universität Bonn -> Institut für Informatik -> Abteilung V