Institut für Informatik
 
Abteilung V

 
Universität Bonn -> Institut für Informatik -> Abteilung V
CS-APX-Reports 2011 Copyright 2011 Universität Bonn, Institut für Informatik, Abt. V
89133

23.11.2011

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

We study the approximation hardness of the Shortest Superstring, the Maximal Compression and the Maximum Asymmetric Traveling Salesperson (MAX-ATSP) problem. We introduce a new reduction method that produces strongly restricted instances of the Shortest Superstring problem, in which the maximal orbit size is eight (with no character appearing more than eight times) and all given strings having length at most six. Based on this reduction method, we are able to improve the best up to now known approximation lower bound for the Shortest Superstring problem and the Maximal Compression problem by an order of magnitude. The results imply also an improved approximation lower bound for the MAX-ATSP problem.

Last Change: 11/05/14 at 10:55:10
 English
Universität Bonn -> Institut für Informatik -> Abteilung V