An approximation algorithm for the shortest common supersequence problem
Paolo Barone, Paola Bonizzoni, Gianluca Della Vedova, Giancarlo Mauri · 2001
In this paper an approximation algorithm, called Reduce-Expand, for the Shortest Common Supersequence (SCS) problem is presented and its behavior is studied experimentally. While the guaranteed approximation ratio of Reduce-Expand matches that of the best known algorithm, our algorithm clearly outperforms such algorithm with respect to the length of the approximate solution.