Abstract:
This paper presents two simple approximation algorithms for the
shortest superstring problem, with approximation ratios 
( 
) and 
( 
), improving the best
previously published 
approximation. 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 semi-infinite
string 
of period q, there exists an integer k,
such that for any (finite) string s of period p which is
inequivalent to 
, the overlap between s and the rotation
is at most 
. Moreover, if 
, then the overlap between s and 
is not larger than
. In the previous shortest superstring algorithms p+q was
used as the standard bound on overlap between two strings with periods p
and q.
Available as PostScript, PDF, DVI.