[Back]

M. Horn, G. Raidl:
"A∗-Based Compilation of Relaxed Decision Diagrams for the Longest Common Subsequence Problem";
Talk: CPAIOR 2021 - 18th International Conference of Integration of Constraint Programming, Artificial Intelligence, and Operations Research, Wien; 2021-07-05 - 2021-07-08; in: "International Conference on Integration of Constraint Programming, Artificial Intelligence, and Operations Research", LNCS / Springer, 12735 (2021), ISBN: 978-3-030-78229-0; 72 - 88.

We consider the longest common subsequence (LCS) problem
and propose a new method for obtaining tight upper bounds on the
solution length. Our method relies on the compilation of a relaxed multivalued
decision diagram (MDD) in a special way that is based on the
principles of A
∗
search. An extensive experimental evaluation on several
standard LCS benchmark instance sets shows that the novel construction
algorithm clearly outperforms a traditional top-down construction
(TDC) of MDDs. We are able to obtain stronger and at the same time
more compact relaxed MDDs than TDC and this in shorter time. For
several groups of benchmark instances new best known upper bounds
are obtained. In comparison to existing simple upper bound procedures,
the obtained bounds are on average 14.8% better.

http://dx.doi.org/10.1007/978-3-030-78230-6_5

https://publik.tuwien.ac.at/files/publik_301799.pdf