A probabilistic PTAS for shortest common superstring

作者：Plociennik Kai^*

来源：Theoretical Computer Science, 2014, 522: 44-53.

DOI：10.1016/j.tcs.2013.12.005

• Shortest common superstring
• Approximation
• Average-case analysis
• Semi-random input
• Greedy superstring

We consider approximation algorithms for the shortest common superstring problem (SCS). It is well known that there is a constant f > 1 such that there is no efficient approximation algorithm for SCS achieving a factor of at most f in the worst case, unless P = NP. We study SCS on random inputs and present an approximation scheme that achieves, for every epsilon > 0, a (1 + epsilon)-approximation in expected polynomial time. We also show that the greedy algorithm achieves approximation ratio 1 + epsilon 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).

• 出版日期2014-2-20