  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 four. 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.
