- 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