Improved inapproximability results for the shortest superstring and related problems
Marek Karpiński, Richard Schmied · 2013
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.