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.
Barone, P., Bonizzoni, P., DELLA VEDOVA, G., Mauri, G. (2001). An Approximation Algorithm for the Shortest Common Supersequence Problem: an Experimental Analysis. In Proceedings of the 2001 ACM symposium on Applied computing (pp.56-60). New York : ACM Press [10.1145/372202.372275].
An Approximation Algorithm for the Shortest Common Supersequence Problem: an Experimental Analysis
BONIZZONI, PAOLA;DELLA VEDOVA, GIANLUCA;MAURI, GIANCARLO
2001
Abstract
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.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
