On improving the approximation ratio of the r-shortest common superstring problem

Tristan Braquelaire, Marie Gasparoux, Mathieu Raffinot +1

The Shortest Common Superstring problem (SCS) consists, for a set of strings S = {s_1,...,s_n}, in finding a minimum length string that contains all s_i, 1<= i <= n, as substrings.…