Improved Lower Bounds for the Shortest Superstring and Related Problems

Details Improved Lower Bounds for the Shortest Superstring and Related Problems Improved Lower Bounds for the Shortest Superstring and Related Problems

2011-11-23

arxiv.org/abs/1111.5442v1

Computer Science

Computational Complexity

Scientific paper

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 character appearing more than eight times) and all given strings having length at most six. Based on this reduction method, we are able to improve the best up to now known approximation lower bound for the Shortest Superstring problem and the Maximal Compression problem by an order of magnitude. The results imply also an improved approximation lower bound for the MAX-ATSP problem.

Affiliated with

Also associated with

No associations

Rating

Improved Lower Bounds for the Shortest Superstring and Related Problems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Improved Lower Bounds for the Shortest Superstring and Related Problems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Improved Lower Bounds for the Shortest Superstring and Related Problems will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-376999