Our research interest focuses on algorithmics, complexity theory and automata theory. Our research projects follow mainly the following two directions:
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.
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.
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.
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.
Diese Website wird in älteren Versionen von Netscape ohne graphische Elemente dargestellt. Die Funktionalität der Website ist aber trotzdem gewährleistet. Wenn Sie diese Website regelmässig benutzen, empfehlen wir Ihnen, auf Ihrem Computer einen aktuellen Browser zu installieren. Weitere Informationen finden Sie auf
The content in this site is accessible to any browser or Internet device, however, some graphics will display correctly only in the newer versions of Netscape. To get the most out of our site we suggest you upgrade to a newer browser.