Talks and Poster Presentations (with Proceedings-Entry):

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.

English abstract:
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.

"Official" electronic version of the publication (accessed through its Digital Object Identifier - DOI)

Electronic version of the publication:

Created from the Publication Database of the Vienna University of Technology.