Approximating Shortest Superstings

The shortest superstring problem is to find a shortest string which contains each string in a given set as substring. The applications are in molecular biology and data compression. The problem is NP-hard and the best previous approximation algorithm achieves approximation guarantee of factor 3. A new algorithm is presented, which finds a supersting that is at most 2.89 times longer than the shortest supersting