View article

The problems of finding shortest common supersequences (SCS) and longest common subsequences (LCS) are two well-known -hard problems that have applications in many areas, including computational molecular biology, data compression, robot motion planning, and scheduling, text editing, etc. A lot of fruitless effort has been spent in searching for good approximation algorithms for these problems. In this paper, we show that these problems are inherently hard to approximate in the worst case. In particular, we prove that (i) SCS does not have a polynomial-time linear approximation algorithm unless ; (ii) There exists a constant such that, if SCS has a polynomial-time approximation algorithm with ratio , where n is the number of input sequences, then is contained in ; (iii) There exists a constant such that, if LCS has apolynomial-time approximation algorithm with performance ratio , then …