direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

AFFA: Algorithmen für Faire Allokationen

Funded by Deutsche Forschungsgemeinschaft (Project AFFA, NI 369/15 and BR5207/1) starting in October 2016.


The main focus of AFFA is the investigation of important computational problems in context of fair allocations with respect to their algorithmic tractability. The goals include basic problems such as the verification of the existence of fair allocations, finding the corresponding allocations, and the computational complexity of specific fixed protocols that find the allocations. Moreover, we want to analyze problems in context of manipulation, bribery, and external control. The underlying problems very often are NP-hard, which also motivates the application of parameterized, approximation, and heuristic approaches. In particular, we want to identify the limits of approximability in polynomial and FPT time. In addition, efficient reductions to established standard solving methods (like highly optimized SAT or ILP solvers) seem promising to find exact solutions for at least for some inputs. Finally, we also plan to test the developed algorithms with respect to their practical usefulness by implementations and experimental investigations and also want to make our software publicly available.

People: Andrzej Kaczmarczyk

Head: Rolf Niedermeier

DAMM: Datenreduktion in der parametrisierten Algorithmik - neue Modelle und Methoden

Funded by Deutsche Forschungsgemeinschaft (Project DAMM, NI 369/13) starting in Dezember 2012.


Preprocessing by means of data reduction rules is a common approach for the algorithmic treatment of combinatorially difficult and compute-intensive problems. Parameterized Algorithmics formalizes the concept of preprocessing in terms of problem kernels. So far, research mainly focussed on the size of the problem kernel and lacked a broader analysis of preprocessing. Thus, the goal of DAMM is to investigate different aspects of preprocessing taking into consideration other interesting properties of problem kernels, such as the running time for example. We also aim at developing kernelizations with respect to "non-standard" and "multivariate" parameterizations which could be of practical interest. Finally, we will consider different kernelization models that generalize the concept of problem kernels, such as Turing kernels, analyzing their relations and possible applications.

People: Till Fluschnik

Head: Rolf Niedermeier

DAPA: Data Driven Parameterized Algorithmics for Graph Modification Problems

Funded by Deutsche Forschungsgemeinschaft (Project DAPA, NI 369/12) starting in January 2012.


Problems from many different fields like biology, operations research and image processing can be modeled as graph modification problems in a simple and elegant fashion. The task is then to modify the structure of a given graph according to particular conditions. Allowed modifications are often as simple as adding edges or deleting vertices or edges. Unfortunately, most graph modification problems are NP-hard, that is, they presumably admit no efficient algorithms for finding the minimum number of modifications needed. However, there is hope for relevant and efficiently solvable special cases because of the following. First, there is often only a small number of modifications needed in practice. Second, the input graphs often obey structures that are specific to the application. Both these observations can be used to create "problem parameterizations" which can be exploited in the development of efficient parameterized algorithms. In this project, finding such parameterizations will be data driven, that is, promising parameterizations will be extracted from "real world" data. We focus on applications in the context of "data clustering" and "planning". Aside from theoretical analyses we will also provide implementations and empirical evaluation.

Head: Rolf Niedermeier

Zusatzinformationen / Extras