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

We prove explicit approximation hardness results for the Graphic TSP on cubic and subcubic graphs as well as the new inapproximability bounds for the corresponding instances of the (1,2)-TSP. The proof technique uses new modular constructions of simulating gadgets for the restricted cubic and subcubic instances. The modular constructions used ... more >>>