Abstract
At CPM 2017, Castelli et al. define and study a new variant of the Longest Common Subsequence Problem, termed the Longest Filled Common Subsequence Problem (LFCS). For the LFCS problem, the input consists of two strings A and B and a multiset of characters M. The goal is to insert the characters from M into the string B, thus obtaining a new string B, such that the Longest Common Subsequence (LCS) between A and B∗ is maximized. Casteli et al. show that the problem is NP-hard and provide a 3/5-approximation algorithm for the problem. In this paper we study the problem from the experimental point of view. We introduce, implement and test new heuristic algorithms and compare them with the approximation algorithm of Casteli et al. Moreover, we introduce an Integer Linear Program (ILP) model for the problem and we use the state of the art ILP solver, Gurobi, to obtain exact solution for moderate sized instances.
| Original language | English |
|---|---|
| Title of host publication | Proceedings - 2018 20th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, SYNASC 2018 |
| Publisher | Institute of Electrical and Electronics Engineers Inc. |
| Pages | 449-453 |
| Number of pages | 5 |
| ISBN (Electronic) | 9781728106250 |
| DOIs | |
| Publication status | Published - Sep 1 2018 |
| Event | 20th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, SYNASC 2018 - Timisoara, Romania Duration: Sep 20 2018 → Sep 23 2018 |
Publication series
| Name | Proceedings - 2018 20th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, SYNASC 2018 |
|---|
Conference
| Conference | 20th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, SYNASC 2018 |
|---|---|
| Country | Romania |
| City | Timisoara |
| Period | 9/20/18 → 9/23/18 |
Fingerprint
Keywords
- Heuristic
- Longest common subsequence
- NP-hard problem
ASJC Scopus subject areas
- Computational Theory and Mathematics
- Software
- Computational Mathematics
- Modelling and Simulation
- Numerical Analysis
Cite this
Heuristic algorithms for the longest filled common subsequence problem. / Mincu, Radu Stefan; Popa, Alexandru.
Proceedings - 2018 20th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, SYNASC 2018. Institute of Electrical and Electronics Engineers Inc., 2018. p. 449-453 8750767 (Proceedings - 2018 20th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, SYNASC 2018).Research output: Chapter in Book/Report/Conference proceeding › Conference contribution
}
TY - GEN
T1 - Heuristic algorithms for the longest filled common subsequence problem
AU - Mincu, Radu Stefan
AU - Popa, Alexandru
PY - 2018/9/1
Y1 - 2018/9/1
N2 - At CPM 2017, Castelli et al. define and study a new variant of the Longest Common Subsequence Problem, termed the Longest Filled Common Subsequence Problem (LFCS). For the LFCS problem, the input consists of two strings A and B and a multiset of characters M. The goal is to insert the characters from M into the string B, thus obtaining a new string B, such that the Longest Common Subsequence (LCS) between A and B∗ is maximized. Casteli et al. show that the problem is NP-hard and provide a 3/5-approximation algorithm for the problem. In this paper we study the problem from the experimental point of view. We introduce, implement and test new heuristic algorithms and compare them with the approximation algorithm of Casteli et al. Moreover, we introduce an Integer Linear Program (ILP) model for the problem and we use the state of the art ILP solver, Gurobi, to obtain exact solution for moderate sized instances.
AB - At CPM 2017, Castelli et al. define and study a new variant of the Longest Common Subsequence Problem, termed the Longest Filled Common Subsequence Problem (LFCS). For the LFCS problem, the input consists of two strings A and B and a multiset of characters M. The goal is to insert the characters from M into the string B, thus obtaining a new string B, such that the Longest Common Subsequence (LCS) between A and B∗ is maximized. Casteli et al. show that the problem is NP-hard and provide a 3/5-approximation algorithm for the problem. In this paper we study the problem from the experimental point of view. We introduce, implement and test new heuristic algorithms and compare them with the approximation algorithm of Casteli et al. Moreover, we introduce an Integer Linear Program (ILP) model for the problem and we use the state of the art ILP solver, Gurobi, to obtain exact solution for moderate sized instances.
KW - Heuristic
KW - Longest common subsequence
KW - NP-hard problem
UR - http://www.scopus.com/inward/record.url?scp=85069542444&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85069542444&partnerID=8YFLogxK
U2 - 10.1109/SYNASC.2018.00075
DO - 10.1109/SYNASC.2018.00075
M3 - Conference contribution
T3 - Proceedings - 2018 20th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, SYNASC 2018
SP - 449
EP - 453
BT - Proceedings - 2018 20th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, SYNASC 2018
PB - Institute of Electrical and Electronics Engineers Inc.
ER -