Improved inapproximability results for the shortest superstring and related problems

Abstract

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.