Wojciech Szpankowski, Purdue University, W. Lafayette, U.S.A.

Greedy algorithms for the shortest common superstring that are asymptotically optimal

There has recently been a resurgence of interest in the shortest common superstring problem due to its 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 $B$ times $(2