Inhalt des Dokuments
Programming by Optimisation Meets Parameterised Algorithmics: A Case Study for Cluster Editing
Dr. rer. nat. Sepp Hartung (TU Berlin)
Inspired by methods and theoretical results from parameterised
algorithmics, we improve the state of the art in solving Cluster
Editing, a prominent NP-hard clustering problem with applications in
computational biology and beyond.
In particular, we demonstrate that an extension of a certain preprocessing algorithm, called the (k+1)-data reduction rule in parameterised algorithmics, embedded in a sophisticated branch & bound algorithm, improves over the performance of existing algorithms based on Integer Linear Programming (ILP) and branch & bound.
Furthermore, our version of the (k+1)-rule outperforms the theoretically most effective preprocessing algorithm, which yields a 2k-vertex kernel. Notably, this 2k-vertex kernel is analysed empirically for the first time here.
Our new algorithm was developed by integrating Programming by Optimisation into the classical algorithm engineering cycle - an approach which we expect to be successful in many other contexts.
Back to the research colloquium site.