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.
No
slide + paper
Scientifica
approximation, algorithms, shortest,common supersequence problem
English
ACM Symposium on Applied Computing
1-58113-287-5
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].
Barone, P; Bonizzoni, P; DELLA VEDOVA, G; Mauri, G
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