TU Berlin

Research Group Algorithmics and Computational ComplexityTalk 29.01.2015

isti-logo

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.

Date
Speaker
Location
Language
29.01.2015
16:15
Sepp Hartung
TEL 512
english

Back to the research colloquium site.

Navigation

Quick Access

Schnellnavigation zur Seite über Nummerneingabe