Nordic Journal of Computing Bibliography

Abstract

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.

Categories and Subject Descriptors: F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems; G.2.1 [Discrete Mathematics]: Combinatorics

Additional Key Words and Phrases: shortest common supersequence, string algorithms, approximation algorithms

Selected references

• Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy. Proof verification and hardness of approximation problems. In 33rd Annual Symposium on Foundations of Computer Science, pages 14-23, Pittsburgh, Pennsylvania, 24-27 October 1992. IEEE.

• Daniel S. Hirschberg. Algorithms for the longest common subsequence problem. Journal of the ACM, 24(4):664-675, October 1977.

• David Maier. The complexity of some problems on subsequences and supersequences. Journal of the ACM, 25(2):322-336, April 1978.

• Robert A. Wagner and Michael J. Fischer. The string-to-string correction problem. Journal of the ACM, 21(1):168-173, January 1974.

Shortcuts: