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. In data compression, the problem is a part of a general model of string compression proposed by Gallant, Maier and Storer (JCSS '80). Much of the recent interest in the problem is due to its application to DNA sequence assembly. The problem has been shown to be NP-hard; in fact, it was shown by Blum et al.(JACM '94) to be MAX SNP-hard. The first O(1)-approximation was also due to Blum et al., who gave an algorithm that always returns a superstring no more than 3 times the length of an optimal solution. Several researchers have published re..