SHORTEST COMMON SUPERSTRING

• INSTANCE: Finite alphabet $\Sigma$, finite set R of strings from $\Sigma^*$.

• SOLUTION: A string $w\in\Sigma^*$ such that each string $x\in R$ is a substring of w, i.e. $w=w_0 x w_1$ where $w_0,w_1\in\Sigma^*$.

• MEASURE: Length of the superstring, i.e., $\vert w\vert$.

  
  

• 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 $O(\log \mbox{\sl opt})$ [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 $\sum_{x\in R} \vert x\vert -\vert w\vert$, is approximable within 2 [450] and [455].

• Garey and Johnson: SR9