A 2 1 2 approximation in algorithm for shortest common superstring
Elizabeth Sweedyk · 1996
Given a set of strings, $S=\{ s\sb1,s\sb2,\...,s\sb{n}\},$ over a finite alphabet $\Sigma$, a common superstring of S is a string that contains each $s\sb{i}$ as a contiguous substring. The Shortest Common Superstring (SCS) problem is to find a common superstring of minimum length. This problem has important applications in computational biology (11) and in data compression (15). SCS has been shown to be MAX SNP-hard (3) so it is unlikely that the length of the shortest common superstring can be approximated within an arbitrary constant. Several heuristics have been suggested and it is conjectured that the GREEDY algorithm achieves an approximation ratio of 2. This, unfortunately, remains an open question. Several linear approximation algorithms for SCS have been proposed. The first by Blum et.al. (3) guarantees a performance factor of three. The factor has been successively improved to $2{8\over9}$ (18), 2${5\over6}$ (4), 2${50\over63}$ (9) and 2${3\over4}$ (1). In this paper we give an algorithm that guarantees a $2{1\over2}$ approximation ratio.