Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Shortest Superstring:
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 >>>

TR15-097 | 16th June 2015
Marek Karpinski

Towards Better Inapproximability Bounds for TSP: A Challenge of Global Dependencies

We present in this paper some of the recent techniques and methods for proving best up to now explicit approximation hardness bounds for metric symmetric and asymmetric Traveling Salesman Problem (TSP) as well as related problems of Shortest Superstring and Maximum Compression. We attempt to shed some light on the ... more >>>

ISSN 1433-8092 | Imprint