Algorithmic Performance Guarantees: Foundations and Applications (APEG)


Project Summary

Optimization problems are ubiquitous in computer science. Almost every problem involves the optimization of some objective function. However a major part of these problems cannot be solved to optimality. Consequently, algorithms that achieve provably good performance guarantees are of immense importance. Considerable progress has already been made, but great challenges remain: Some fundamental problems are not well understood. Moreover, for important problems arising in new applications, no solutions are known at all.

The goal of APEG is to significantly advance the state-of-the-art in the field of algorithmic performance guarantees. Specifically, the project has two missions: First, it will develop new algorithmic techniques in the areas of online algorithms, approximation algorithms and algorithmic game theory. Second, it will apply these techniques to solve fundamental problems that are central to these algorithmic disciplines. APEG will attack long-standing open problems. Furthermore, it will formulate and investigate new algorithmic problems that arise in modern applications. The research agenda encompasses a broad spectrum of classical and timely topics including (a) resource allocation in computer systems, (b) data structuring, (c) graph problems, with relations to Internet advertising, (d) complex networks and (e) massively parallel systems. In addition to basic optimization objectives, the project will also study the new performance metric of energy minimization in computer systems.

Affiliated Researchers


Lehrstuhl für Algorithmen und Komplexität
Prof. Dr. Susanne Albers

Boltzmannstr. 3
85748 Garching bei München

Tel +89.289.17706
Fax +89.289.17707