|
|
| |
| 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
|
Universität Bonn -> Institut für Informatik -> Abteilung V | |