# Algorithms & Complexity

The cluster members pursue a wide spectrum of foundational and applied working directions in algorithms research. We design algorithms and analyze their performance in terms of a desired quality measure. Our research foci include the study of approximation and online algorithms, randomized algorithms as well as parallel and network algorithms. We specifically investigate fundamental algorithmic problems arising in the resource management of computer systems and large networks. A recent line of work addresses the design of energy-efficient algorithms. Moreover, our research interests include the fields of algorithmic game theory and algorithms engineering. On the more applied side, the cluster members explore fundamental algorithmic and complexity issues in computational logic, program and systems verification as well as mathematical optimization, computer vision and scientific computing. In this context we study various measures of complexity and efficiency. Moreover, we design massively parallel algorithms.

## Exemplary Projects

### Energy-Efficient Scheduling

Partner: Prof. Susanne Albers

This project investigates algorithmic techniques for energy savings in hardware environments, thereby supporting the processing of big data sets on the systems level. It focuses on the technique of dynamic speed scaling. Most of the prior work makes idealized architectural assumptions: A processor would have a continuous unbounded speed spectrum, and speed changes could be performed at any time at no cost. We will design and analyze algorithms for the realistic scenario that a processor has a finite set of discrete speed levels. The theoretically oriented work will be complemented by thorough experiments, forming an algorithms engineering part of the project. A specific project goal is to bring algorithmic results closer to practice.

### Gottfried Wilhelm Leibniz-Prize for Prof. Susanne Albers

The grant supported research on a wide, almost unlimited spectrum of topics in the design and analysis of algorithms, algorithmic game theory and algorithm engineering. The scientific work focuses on advances in online and approximation algorithms, the study of fundamental resource management and scheduling problems, network design games and algorithms for energy conservation.

### Geometric Reconstruction in Refraction and Diffraction-Based Tomography

Partner: Prof. Peter Gritzmann

Mathematical modelling and analysis of problems in (dynamic) tomography. Development of algorithms (based on geometry and combinatorial optimization).

### Degree Bounds for Gröbner Bases of Important Classes of Polynomial Ideals and Efficient Algorithms

Partner: Prof. Ernst Mayr

In his PhD thesis in 1965, Buchberger introduced Gröbner bases in order to solve problems of polynomial algebra algorithmically. The most fundamental example is the membership problem for ideals, i.e. to decide whether a given polynomial is a member of a given ideal. He was able to present an algorithm to calculate a Gröbner basis for any ideal. At first, the complexity of the algorithm was unknown. Small examples worked quite well, and many improvements to the algorithm as well as new approaches were suggested consecutively. For large examples, however, all algorithms quickly reached the limits set by resources like time and memory (space). Especially Gröbner bases with many variables only could be computed rarely. This behaviour is unavoidable as shown by Mayr and Meyer. More precisely, a lower space bound for the membership problem in polynomial ideals, exponential in the number of variables, was established. Since Gröbner bases can be used to solve the membership problem easily, their computation must be hard, too. The task of our project within SPP1489 now is to find interesting cases, where the membership problem is demonstrably easier (and thus possibly better treatable in practice). So far, we have achieved new and exact complexity results for the membership problem in general polynomial ideals as a function of the dimension of the ideal, as well as numerous new (and vastly improved) upper bounds for polynomial ideal problems restricted to radical binomial ideals.