Department of Computer Science
 
Chair V

 
University of Bonn -> Department of Computer Science -> Chair V
CS-APX-Reports 2012 Copyright 2012 University of Bonn, Department of Computer Science, Abt. V
89139

27.08.2012

Improved Inapproximability Results for the Shortest Superstring and Related Problems
Marek Karpinski and Richard Schmied
[Download PostScript] [Download PDF]

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

Last Change: 11/05/14 at 10:59:29
 Deutsch 		University of Bonn -> Department of Computer Science -> Chair V