Next: LONGEST COMMON SUBSEQUENCE Up: Compression and Representation Previous: SHORTEST COMMON SUPERSEQUENCE Index

### SHORTEST COMMON SUPERSTRING

- INSTANCE: Finite alphabet , finite set R of strings from .

- SOLUTION: A string such that each string is a substring of w, i.e. w=w0 x w1 where .

- MEASURE: Length of the superstring, i.e., |w|.

- Good News: Approximable within 2.75 [30].

- Bad News: APX-complete [78].

- 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 [339]. 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 [259]. The complementary MAXIMUM COMPRESSION problem, where the objective is to maximize , is approximable within 2 [427] and [432].

- Garey and Johnson: SR9