Experimenting an Approximation Algorithm for the LCS
Paola Bonizzoni, Mauro Mariotti d’Alessandro, Gianluca Della Vedova, Giancarlo Mauri · 1998
In this paper, we give a new approximation algorithm, the Expansion algorithm, for the longest common subsequence problem. We prove that the Expansion algorithm has in the worst case a guaranteed performance ratio which is not worse than the one of the Long Run algorithm. Furthermore, it is given experimental evidence that, for most problem instances, Expansion algorithm achieves an error ratio better than the one achieved by the Long Run. In particular, while Long Run gives the optimal solution only when this one is a uniform sequence (0 n , 1 n ), Expansion outputs an optimal solution in a significant part of the cases. 1 Introduction The problem of the longest common subsequence (LCS) is a well-known NP -hard problem [7]. For two finite sequences s = s 1 s 2 \\Delta \\Delta \\Delta s m , t = t 1 t 2 \\Delta \\Delta \\Delta t n over alphabet \\Sigma, the LCS problem consists of finding the longest sequence u 1 u 2 \\Delta \\Delta \\Delta u r such that there exist indices i 1 ! i 2 \\Delta ...