TU Berlin

Algorithmics and Computational Complexity Research GroupTalk 29.01.2015


Page Content

to Navigation

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.

Sepp Hartung
TEL 512

Back to the research colloquium site.


Quick Access

Schnellnavigation zur Seite über Nummerneingabe