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.
slide + paper
approximation, algorithms, shortest,common supersequence problem
English
ACM Symposium on Applied Computing
2001
Proceedings of the 2001 ACM symposium on Applied computing
1-58113-287-5
2001
56
60
none
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].
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10281/12248
Citazioni
  • Scopus 25
  • ???jsp.display-item.citation.isi??? ND
Social impact