Publica
Hier finden Sie wissenschaftliche Publikationen aus den FraunhoferInstituten. A probabilistic PTAS for shortest common superstring
 Theoretical computer science 522 (2014), pp.4453 ISSN: 03043975 

 English 
 Journal Article 
 Fraunhofer ITWM () 
Abstract
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).