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