Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Hybrid Problem:
TR11-156 | 23rd November 2011
Marek Karpinski, Richard Schmied

Improved Lower Bounds for the Shortest Superstring and Related Problems

Revisions: 1

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

TR13-066 | 25th April 2013
Marek Karpinski, Richard Schmied

Approximation Hardness of Graphic TSP on Cubic Graphs

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

ISSN 1433-8092 | Imprint