Rotation of Periodic Strings and Short Superstring

We give two simple approximation algorithm with ratios $2\frac{2}{3}$ and $2\frac{25}{42}$ for the shortest superstring problem. The best previously published approximation ratio was $2\frac{3}{4}$ due to Armen and Stein. The framework of our improved algorithms is similar to previous algorithms in the sense that it constructs a superstring by computing some optimal cycle covers on the distance graph of the given strings, and then breaks and merges the cycles to finally obtain a Hamiltonian path. However we make use of a new bound on the overlap between a periodic string and any other string with equal or smaller period. Joint work with Tao Jiang and Zhigen Jiang.