A Greedy Algorithm for the Shortest Common Superstring is Asymptotically Optimal
ALAN M. FRIEZE, Wojciech Szpankowski · Purdue e-Pubs (Purdue University System) · 1995
There has recently been a resurgence of interest in the shortest common superstring problem due to important applications in molecular biology (e.g., recombination of DNA) and data compression.The problem is NP-hard, but it has been known for some time that greedy algorithms work well for this problem.More precisely, it was proved in a recent sequence of papers that in the worst case a greedy algorithm produces a superstring that is at most f3 times (2 ~f3 ~3) worse than optimal.We analyze the problem in a probabilistic framework, and consider the total overlaps O~pl and O~~prod uced respectively by the optimal algorithm and a greedy one which turn out to be asymptotically equivalent.More precisely, we show that with high probability lim n . . . . .oo n~~