On Solving the Minimum Common String Partition Problem by Decision Diagrams

Miloš Chromý, Markus Sinnl

2022

Abstract

In the Minimum Common String Partition Problem (MCSP), we are given two strings on input, and we want to partition both into the same collection of substrings, minimizing the number of the substrings in the partition. This combinatorial optimization problem has applications in computational biology and is NP-hard. Many different heuristic and exact methods exist for this problem, such as a Greedy approach, Ant Colony Optimization, or Integer Linear Programming. In this paper, we formulate the MCSP as a Dynamic Program and develop an exact solution algorithm based on Decision Diagrams for it. We also introduce a restricted Decision Diagram that allows to compute heuristic solutions to the MCSP and compare the quality of solution and runtime on instances from literature with existing approaches. Our approach scales well and is suitable for heuristic solutions of large-scale instances.

Paper Citation

in Harvard Style

Chromý M. and Sinnl M. (2022). On Solving the Minimum Common String Partition Problem by Decision Diagrams. In Proceedings of the 11th International Conference on Operations Research and Enterprise Systems - Volume 1: ICORES, ISBN 978-989-758-548-7, pages 177-184. DOI: 10.5220/0010830200003117

in Bibtex Style

@conference{icores22,
author={Miloš Chromý and Markus Sinnl},
title={On Solving the Minimum Common String Partition Problem by Decision Diagrams},
booktitle={Proceedings of the 11th International Conference on Operations Research and Enterprise Systems - Volume 1: ICORES,},
year={2022},
pages={177-184},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0010830200003117},
isbn={978-989-758-548-7},
}

in EndNote Style

TY - CONF

JO - Proceedings of the 11th International Conference on Operations Research and Enterprise Systems - Volume 1: ICORES,
TI - On Solving the Minimum Common String Partition Problem by Decision Diagrams
SN - 978-989-758-548-7
AU - Chromý M.
AU - Sinnl M.
PY - 2022
SP - 177
EP - 184
DO - 10.5220/0010830200003117