direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

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.

Sepp Hartung
TEL 512

Back to the research colloquium site.

Zusatzinformationen / Extras