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 |
(local if available)