Algorithms & Complexity

Algorithms and Complexity covers a wide range of fundamental and applied work directions in algorithms research. It aims to develop algorithms and analyze their performance with regard to a desired quality measure. The research foci include

• Approximation- and online algorithms. They should help to develop approximate solutions for problems that are difficult or impossible to solve exactly. Algorithms and Complexity aims to develop algorithms that achieve provably good behavior. In particular, problems are examined that occur in the resource management of computer systems, in large networks and in data structuring.
• Randomized Algorithms. In many cases, randomized algorithms are easier to understand, simpler to implement, and more efficient than deterministic algorithms for the same problem. Algorithms and Complexity develops and analyzes randomized algorithms for fundamental optimization problems.
• Parallel- and Network Algorithms. Network and graph algorithms are used to optimize processes in a wide variety of application areas. Research in the field of parallel algorithms examines parallel computer architectures and develops parallel algorithms for fundamental problems.
• Algorithmic Game Theory. This is a young research area at the interface of theoretical computer science, mathematics and business administration, as it deals with optimal strategic behavior in interactive situations.
• Algorithm engineering. In some areas, research has already successfully contributed to bridging the gap between theory and practice. Prime examples are the rapid progress that could be achieved through new algorithms for route planning or the search function in texts. In the research area Algorithms and Complexity, experimental studies are carried out in which the research results obtained through mathematical analyzes are validated.
• Energy-efficient algorithms. Since computing and data centers are also affected by the sharp rise in energy costs, the cluster is investigating algorithmic techniques that reduce the energy requirements in computer systems.

In the applications area, Algorithms and Complexity investigates fundamental algorithmic and complexity-theoretical problems in computational logic, program and system verification, mathematical optimization, image recognition and scientific computing. In this context, they study various measures of efficiency and complexity. In addition, algorithms are developed for massively parallel architectures in which a huge number of processors are connected via a network.

DFG Priority Programme 1736 "Algorithms for Big Data"

Algorithms for BIG DATA

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.

Energy-efficient Scheduling

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.

Gottfried Wilhelm Leibniz-Preis

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.

GBiC PolyA