Department of Computer Science | Institute of Theoretical Computer Science
Here we describe some selected research activities of our groups. For complete lists follow these links:
In average case analysis one considers the typical behaviour of an algorithm. From a practical point of view this is in particular important if the worst case analysis is not satisfactory: it is possible that an algorithm provides empirically good results, even though it has a bad worst case behaviour. The aim of this project is to develop new models and analysis methods for the average case analysis of algorithms.
In the last couple of years new exciting combinatorial models for geometric optimization problems have emerged. For several linear complementarity problems these new combinatorial abstractions provide the only available algorithms with nontrivial running time guarantees. Within this new project, we explore unique-sink orientations, strong LP-type problems, as well as algorithms for problems fitting into the respective models.
Many algorithmic research problems in wireless and/or mobile networks turn out to be variants of classic graph theory and/or computational geometry problems. In this work we try to understand the basic algorithmic foundations and principles of mobile information and communication systems.