Algorithmics and Computational Complexity

The Art of Difference Parameterization in Multivariate Algorithmics (DiPa)

Synopsis

Further developing and analyzing analytical tools such as ``difference parameterization'' (a core example is the established framework of above-guarantee parameterization), we aim at achieving (practically) more meaningful statements about theperformance of exact (fixed-parameter) algorithms for NP-hard problems. To this end, our focus is on employing search trees and data reduction techniques as core algorithmic tools, and methods from parameterized complexity analysis as core theoretical tools.Our key lines of attack concern- to study difference parameters through lower bounds achieved via packing of combinatorial structures; - to study difference parameters gained through approximation algorithms, also including linear programming; - to study difference parameters resulting through systematic exploration of structural parameter hierarchies; and - to study linear combinations of parameters, thus generalizing the concept of difference parameters.The utmost goal is to significantly push the “art of problem parameterization'' towards the next level, particularly making the performance of branch & bound (search tree) algorithms better explainable on the one side, and to potentially improve algorithmic approaches (by exploring and exploiting further refined parameterizations) on the other side. Our studies shall mainly focus on NP-hard graph problems.

Funded by

Deutsche Forschungsgemeinschaft (Project DiPa, NI 369/21)

Time

Since March 2021

Head: formerly Rolf Niedermeier, since 2022:

People

Organization name Algorithmics and Computational Complexity
Office TEL 5-1
Room TEL 509A