Next: LONGEST COMMON SUBSEQUENCE
Up: Compression and Representation
Previous: SHORTEST COMMON SUPERSEQUENCE
Finite alphabet ,
finite set R of strings from .
such that each string
is a substring
of w, i.e.
Length of the superstring, i.e., .
- Good News:
Approximable within 2.75 .
- Bad News:
Transformation from MINIMUM METRIC TRAVELING SALESPERSON PROBLEM with distances one and two.
Variation in which there are negative strings in the input and a
solution cannot contain any negative string as a substring, is
If the number of negative strings is constant, or if no negative strings
contain positive strings as substrings, the problem is approximable within
a constant .
The complementary MAXIMUM COMPRESSION problem, where the objective is to
is approximable within 2 
- Garey and Johnson: SR9