Approximation algorithms for the shortest common supersequence
Campbell B. Fraser, Robert W. Irving · Nordic journal of computing · 1995
It is well known that the problem of finding a shortest common supersequence (SCS) of k strings is NP-hard. In this paper we analyse four natural polynomial-time approximation algorithms for the SCS from the point of view of worst-case performance guarantee, expressed in terms of k. All four algorithms behave badly in the worst case, whether the underlying alphabet is unbounded or of fixed size. For a Tournament style algorithm proposed by Timkovsky, we show that the length of the SCS found is between (k + 2)/4 and (3k + 2)/8 times the length of the optimal in the worst case. The corresponding lower bound proved for two obvious Greedy algorithms, Greedy1 and Greedy2, is (4k + 5)/27 and the corresponding upper bounds are (k + e - 1)/e (e = 2.718...) and (k+3)/4 respectively. In the case of the so-called Majority-Merge algorithm of Jiang and Li, no worst-case guarantee beyond the trivial factor of k is possible. Even for a binary alphabet, no constant performance guarantee is possible for any of the four algorithms, in contrast with the guarantee of 2 provided by a trivial algorithm in that case.