Rheinische Friedrich-Wilhelms-Universität Bonn Institut für Informatik
 
Abteilung V

 
Universität Bonn -> Institut für Informatik -> Abteilung V
CS-APX-Reports 2012 Copyright 2012 Universität Bonn, Institut für Informatik, 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
 English
Universität Bonn -> Institut für Informatik -> Abteilung V

Powered by Zope