Next: LONGEST COMMON SUBSEQUENCE
Up: Compression and Representation
Previous: SHORTEST COMMON SUPERSEQUENCE
  Index
- INSTANCE:
Finite alphabet
,
finite set R of strings from
.
- SOLUTION:
A string
such that each string
is a substring
of w, i.e.
where
.
- MEASURE:
Length of the superstring, i.e.,
.
- Good News:
Approximable within 2.75 [32].
- Bad News:
APX-complete [84].
- Comment:
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
approximable within
[357].
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 [274].
The complementary MAXIMUM COMPRESSION problem, where the objective is to
maximize
,
is approximable within 2 [450]
and [455].
- Garey and Johnson: SR9
Viggo Kann
2000-03-20