Next: SHORTEST COMMON SUPERSTRING
Up: Compression and Representation
Previous: Compression and Representation
  Index
- INSTANCE:
Finite alphabet
,
finite set R of strings from
.
- SOLUTION:
A string
such that each string
is a subsequence
of w, i.e. one can get x by taking away letters from w.
- MEASURE:
Length of the supersequence, i.e.,
.
- Good News:
Approximable within
[169].
- Bad News:
Not in APX [275].
- Comment:
Transformation from MINIMUM FEEDBACK VERTEX SET and self-improvability.
Not approximable within
for some
unless
NP
QP [275].
APX-complete if the size of the alphabet
is fixed [275]
and [89].
Variation in which the objective is to find the longest minimal common
supersequence (a supersequence that cannot be reduced to a shorter common
supersequence by removing a letter) is APX-hard even over the binary alphabet,
and SHORTEST MAXIMAL COMMON NON-SUPERSEQUENCE
is APX-hard even over the binary alphabet [376].
Variation in which the longest common subsequence is known is also
APX-hard even over the binary alphabet [133].
- Garey and Johnson: SR8
Next: SHORTEST COMMON SUPERSTRING
Up: Compression and Representation
Previous: Compression and Representation
  Index
Viggo Kann
2000-03-20