Department 1: Algorithms and Complexity

The Algorithms and Complexity Department is headed by Prof. Dr. Kurt Mehlhorn.

The department investigates a broad range of theoretical and practical aspects of modern algorithmics. We design new algorithms and algorithmic techniques, analyze their efficiency and the quality of their solutions, develop provably efficient and correct software, and package our programs in software libraries. The strength of our approach lies in the fact that we consider these aspects in unity and not in isolation.

Research Areas

Combinatorics, Computing, and Randomness

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.

Combinatorial Optimization

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.

Geometry and Algebra

We work on efficient algorithms in the areas of computational geometry and topology. Our focus lies on approaches that relates these areas to computer algebra; in particular, we investigate efficient methods for handling curves and surfaces defined by algebraic equations and for understanding the topological structure of geometric data. We also make our algorithmic results available in mature software libraries such as CGAL.

Algorithmic Game Theory

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.

Theory of Distributed and Embedded Systems

Broadly speaking, distributed computing concerns systems that consist of multiple agents that act based on local information. The main challenge is typically how agents gain access to sufficient information to collaboratively solve a task quickly, despite limits on communication, faults, or inaccurate data.

Overview

People

Who is Who? - Secretaries, Researchers, Students, Guests, Former Staff Members, Former Students, and Former Guests.

Research

What we work on. Who works in which area? Biennial Report 2011.

Offers

Positions, Long Term Visits, Postdoc Positions, Ph.D. Applications, Internships and other Offers.

Teaching

Lectures, Seminars, Bachelor and Master Theses.

Talks & Events

Seminar program, Advanced Mini Courses.

Publications

PhD Theses, Diploma Theses, Publications of Group Members.

Useful Links

Collection of useful Links to Internet Sites.

ADFOCS

Advanced Course on the Foundations of Computer Science

HDT 2017

6th Workshop on Advances in Distributed Graph Algorithms