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., |w|.
- Good News:
Approximable within (|R|+3)4 [156].
- Bad News:
Not in APX [260].
- Comment:
Transformation from MINIMUM FEEDBACK VERTEX SET and self-improvability.
Not approximable within
for some
unless
NP
[260].
APX-complete if the size of the alphabet
is fixed [260]
and [82].
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 [356].
Variation in which the longest common subsequence is known is also
APX-hard even over the binary alphabet [123].
- Garey and Johnson: SR8
Next: SHORTEST COMMON SUPERSTRING
Up: Compression and Representation
Previous: Compression and Representation
  Index
Viggo Kann
1999-04-22