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 helped bridge the gap between theory and practice. Prime examples include the rapid progress that could be achieved through new algorithms for route planning or text search. In the research area of Algorithms and Complexity, experimental studies are conducted to validate the results obtained through mathematical analyses.
• 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.