Research

Our research interest focuses on algorithmics, complexity theory and automata theory. Our research projects follow mainly the following two directions:

• Comparison of the computational power of nondeterminism, randomness and determinism in distinct scenarios and also with respect to the amount of nondeterminism and randomness available. These questions are also considered in relation to the descriptional complexity of distinct computing models.

• Investigating the hardness of discrete optimization problems and designing algorithms for hard problems. We take a special interest in approximation algorithms and in the hardness of reoptimization.

Our Research Projects

Solution Quality and Efficiency in Discrete Optimization

For many practically relevant optimization problems, computing an optimal solution, or even an approximation of it, is computationally intractable in general. One common approach for handling such problems is to design approximation algorithms for restricted classes of input instances. The concept of stability of approximation tries to measure to what extent these algorithms can also be useful for more general classes of inputs. We are investigating this stability concept for different important optimization problems like, e.g., the traveling salesman problem or connectivity problems in graphs obeying some generalized
version of the triangle inequality.

Download PDF >>>

Advice Complexity of Online Algorithms

In the setting of online problems, an algorithm gets his input piecewise and has to produce a part of the final output for each received input part. The most common measure for analyzing the quality of such an online algorithm is the competitive ratio comparing the quality of the computed online solution to the quality of an optimal offline solution, i.e., a solution computed after knowing the complete input. In this project, we propose to look at another quality measure for algorithms having to deal with partial information which hopefully leads to a better understanding of the nature of online problems.

Download PDF >>>

On the Computational Complexity of Reoptimization

In this project, we consider the following reoptimization scenario: Given an instance of a hard optimization problem together with an optimal solution, we want to find a high-quality solution for a locally modified instance. The naturally arising question is whether the knowledge of an optimal solution to the unaltered instance can help in solving the locally modified instance. We are investigating several important optimization problems like, e.g., the Steiner tree problem
and the shortest common superstring problem, in this framework.

Download PDF >>>

Computation Power of Randomization and Nondeterminism

The fundamental questions of computation theory are related to the relative
power of determinism, nondeterminism, and randomization. Currently, one is not able to solve problems about the relations between deterministic, randomized, and nondeterministic polynomial-time classes, and our methods are not powerful enough to give us a realistic chance to attack these problems seriously. Instead, we are trying to estimate the relations between determinism, nondeterminism, and different modes of randomization in distinct restricted frameworks within this project, in order to gain experience with different computation modes and a deeper understanding of the nature of randomization and nondeterminism.

Download PDF >>>