A 2 2/3-Approximation Algorithm for the Shortest Superstring Problem

Given a collection of strings S = fs 1 ; : : : ; s n g over an alphabet \Sigma, a superstring ff of S is a string containing each s i as a substring; that is, for each i, 1 i n, ff contains a block of js i j consecutive characters that match s i exactly. The shortest superstring problem is the problem of finding a superstring ff of minimum length. The shortest superstring problem has applications in both data compression and computational biology. It was shown by Blum et al. [3] to be MAX SNP-hard. The first O(1)-approximation algorithm also appeared in [3], which returns a superstring no more than 3 times the length of an optimal solution. Prior to the algorithm described in this paper, there were several published results that improved on the approximation ratio; of these, the best is our algorithm ShortString, a 2 3 4 --approximation [1]. We present our new algorithm, G-ShortString, which achieves a ratio of 2 2 3 . Our approach builds on the work in [1], in which we identifi..