max planck institut
informatik
informatik
The following groups exist in the department:
We study fundamental algorithmic problems that arise in various fields of mathematics and computer science. Historically we have focused on problems in graph theory, algebra, data structures, and approximation and online algorithms. Discrete Mathematics deals with finite objects, which usually do not have an algebraic structure. Examples are graphs, sequences or set systems. Since such objects play a central role in computer science, there is a rich exchange between the two fields.
Many real world applications are naturally formulated as combinatorial optimization problems, i.e. problems of finding the best solution(s) out of a finite set. Various methods have been developed to tackle such problems: integer programming, fixed-parameter tractable and exact algorithms, approximation algorithms and combinatorial algorithms, among others. D1 works on applying these methods to various problems from different areas, ranging from bioinformatics to geometry, to scheduling, and several others.
We consider general purpose algorithms that are often inspired by optimization processes observed in nature. Such algorithms can be easily applied to a wide range of problems without much problem knowledge. Many general purpose algorithms belong to the field of bio-inspired computation. We consider bio-inspired computation methods from a theoretical point of view and give guidelines how to develop good algorithms for applications.
We work on high quality software libraries in the field of Algorithms and Data Structures (LEDA), External Memory Algorithms (STXXL) and Computational Geometry (CGAL and EXACUS), For EXACUS our interest also lies in algorithms for handling curves and surfaces and the use of computer algebra in geometric computing.
In the problems we consider in this group, we usually try to optimize some goal function while dealing with selfish agents that may have separate and conflicting goals, and that may lie to us in order to improve their own goal function. In algorithmic mechanism design, we ensure that it is in the best interest of the agents to tell us the truth. We also examine the price of anarchy and price of stability for various problems.
A detailed report of our work is given in the Biennial Report 2009 (120 MB).