Efficient Algorithms for Hard Problems

Vision and Research Strategy

When dealing with NP-hard combinatorial problems, one of the common approaches is to derive efficient preprocessing algorithms by means of data reduction rules, for instance, the commercial integer linear program solver CPLEX. The notion of kernelization in parameterized complexity theory provides a natural formalism for the provable measurement of the effectiveness of the preprocessing algorithms.

Our group's research focuses on developing general algorithm design techniques for kernelizations, investigating upper and lower kernel bounds for concrete problems, examining the applicability of kernelizations in such diverse application fields as bioinformatics and artificial intelligence, and studying the algorithm engineering aspect of kernelizations. Moreover, we are also interested in the more general parameterized algorithmics.

Composition of Group

The group Efficient Algortihms for Hard Problems was set up in August 2009. In January 2010 Dr. Martin Dörnfeld joined the group as a postdoc. Peng Sun, a PhD student jointly advised by Jan Baumbach (MMCI), joined in October 2010. The main research topic of the group is to design and implement algorithms for NP-hard problems arising from applications ranging from bioinformatics to multi-agent systems. In particular, we are interested in provably effective preprocessing techniques.

Research Topics and Achievements

Projects and Collaborations

Dr. Jiong Guo

Dr. Jiong Guo

Jiong Guo headed of the Junior Research Group Efficient Algorithms for Hard Problems  from August 2009 until July 2014.