Heuristic algorithms for the longest filled common subsequence problem

Radu Stefan Mincu, Alexandru Popa

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 languageEnglish
Title of host publicationProceedings - 2018 20th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, SYNASC 2018
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages449-453
Number of pages5
ISBN (Electronic)9781728106250
DOIs
Publication statusPublished - Sep 1 2018
Event20th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, SYNASC 2018 - Timisoara, Romania
Duration: Sep 20 2018Sep 23 2018

Publication series

NameProceedings - 2018 20th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, SYNASC 2018

Conference

Conference20th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, SYNASC 2018
CountryRomania
CityTimisoara
Period9/20/189/23/18

Fingerprint

Approximation algorithms
Heuristic algorithms
Subsequence
Heuristic algorithm
Computational complexity
Longest Common Subsequence
Strings
Integer Program
Linear Program
Approximation Algorithms
Multiset
NP-complete problem
Exact Solution

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

Mincu, R. S., & Popa, A. (2018). Heuristic algorithms for the longest filled common subsequence problem. In Proceedings - 2018 20th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, SYNASC 2018 (pp. 449-453). [8750767] (Proceedings - 2018 20th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, SYNASC 2018). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/SYNASC.2018.00075

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 proceedingConference contribution

Mincu, RS & Popa, A 2018, Heuristic algorithms for the longest filled common subsequence problem. in Proceedings - 2018 20th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, SYNASC 2018., 8750767, Proceedings - 2018 20th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, SYNASC 2018, Institute of Electrical and Electronics Engineers Inc., pp. 449-453, 20th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, SYNASC 2018, Timisoara, Romania, 9/20/18. https://doi.org/10.1109/SYNASC.2018.00075
Mincu RS, Popa A. Heuristic algorithms for the longest filled common subsequence problem. In 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). https://doi.org/10.1109/SYNASC.2018.00075
Mincu, Radu Stefan ; Popa, Alexandru. / Heuristic algorithms for the longest filled common subsequence problem. Proceedings - 2018 20th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, SYNASC 2018. Institute of Electrical and Electronics Engineers Inc., 2018. pp. 449-453 (Proceedings - 2018 20th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, SYNASC 2018).
@inproceedings{335a2ba5aa834773ac8d298eb517c2e5,
title = "Heuristic algorithms for the longest filled common subsequence problem",
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.",
keywords = "Heuristic, Longest common subsequence, NP-hard problem",
author = "Mincu, {Radu Stefan} and Alexandru Popa",
year = "2018",
month = "9",
day = "1",
doi = "10.1109/SYNASC.2018.00075",
language = "English",
series = "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",
booktitle = "Proceedings - 2018 20th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, SYNASC 2018",
address = "United States",

}

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 -