ECCC-Report TR11-156https://eccc.weizmann.ac.il/report/2011/156Comments and Revisions published for TR11-156en-usWed, 08 Aug 2012 15:21:44 +0300
Revision 1
| Improved Lower Bounds for the Shortest Superstring and Related Problems |
Marek Karpinski,
Richard Schmied
https://eccc.weizmann.ac.il/report/2011/156#revision1We 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 six
(with no character appearing more than six times) and all given strings having length at most four.
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.Wed, 08 Aug 2012 15:21:44 +0300https://eccc.weizmann.ac.il/report/2011/156#revision1
Paper TR11-156
| Improved Lower Bounds for the Shortest Superstring and Related Problems |
Marek Karpinski,
Richard Schmied
https://eccc.weizmann.ac.il/report/2011/156We 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.Wed, 23 Nov 2011 11:48:47 +0200https://eccc.weizmann.ac.il/report/2011/156