A probabilistic PTAS for shortest common superstring

We consider approximation algorithms for the shortest common superstring problem (SCS). It is well known that there is a constant f>1f>1 such that there is no efficient approximation algorithm for SCS achieving a factor of at most f   in the worst case, unless P=NPP=NP. We study SCS on random inputs and present an approximation scheme that achieves, for every ε>0ε>0, a (1+ε)(1+ε)-approximation in expected polynomial time. We also show that the greedy algorithm achieves approximation ratio 1+ε1+ε with probability exponentially close to 1. These results apply not only if the letters are chosen independently at random, but also to the more realistic mixing model, which allows dependencies among the letters of the random strings. Our results are based on a sharp tail bound on the optimal compression, which improves a previous result by Frieze and Szpankowski (1998).