Department of Computer Science
 
Chair V

 
University of Bonn -> Department of Computer Science -> Chair V
CS-APX-Reports 2013 Copyright 2013 University of Bonn, Department of Computer Science, 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
 Deutsch 		University of Bonn -> Department of Computer Science -> Chair V