Rotations of periodic strings and short superstrings

This paper presents two simple approximation algorithms for the shortest superstring problem with approximation ratios 2 2/3 (approximate to 2.67) and 2 25/42 (approximate to 2.596). The framework of our improved algorithms is similar to that of previous algorithms in the sense that they construct a superstring by computing some optimal cycle covers on the distance graph of the given strings and then break and merge the cycles to finally obtain a Hamiltonian path, but we make use of new bounds on the overlap between two strings. We prove that for each periodic semiinfinite string alpha = a(1)a(2) ... of period q, there exists an integer k, such that for any (finite) string s of period p which is inequivalent to alpha, the overlap between s and the rotation alpha[k] = a(k)a(k+1)... is at most p + 1/2q. Moreover, if p less than or equal to q, then the overlap between s and alpha[k] is not larger than 2/3(p + q). The bounds are tight. In the previous shortest superstring algorithms p + q was used as the standard (tight) bound on overlap between two strings with periods p and q. (C) 1997 Academic Press.