Improved Inapproximability Results for the Shortest Superstring and Related Problems

Karpinski, M. and Schmied, R.

    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.
Cite as: Karpinski, M. and Schmied, R. (2013). Improved Inapproximability Results for the Shortest Superstring and Related Problems. In Proc. Theory of Computing 2013 (CATS 2013) Adelaide, Australia. CRPIT, 141. Wirth, A. Eds., ACS. 27-36
pdf (from crpit.com) pdf (local if available) BibTeX EndNote GS