My group has worked in algorithm engineering for 10 years. In particular, we designed highly successful algorithms in the area of scalable graph algorithms in particular for large inputs. This includes algorithms graph partitioning, algorithms that use graph partitioning, numerics, graph separators, scalable sorting, graph generation, graph visualization, graph drawing, minimum cuts, longest path computations and many more. Most often this results in the release of implementations as open source software libraries, making the latest innovations available to researchers and users all over the world. In particular, the graph partitioning library KaHiP (Karlsruhe High Quality Partitioning) has been downloaded more than a thousand times and is used by many researchers as well as in many applications.

Having experienced how much impact algorithm engineering can have for concrete applications, in particular by working together with application researchers that use the developed algorithms, it is our strong desire to repeat this success by engineering theoretically well-performing approaches to work well in practice. This also includes engineering new techniques that are inspired by currently published theory. In turn, important insights found by this research will provide a basis for further theoretical studies Thus, the goal of this project is to undertake ground-breaking research on algorithm engineering problems that have impact and contribute to the advancement of science in algorithm engineering as well as in the fields of application.

Traditionally, algorithms are designed using simple models of problems and machines. In turn, important results are provable, such as performance guarantees for all possible inputs. This often yields elegant solutions being adaptable to many applications with predictable performance for previously unknown inputs. In algorithm theory, however, taking up and implementing an algorithm is part of the application development. Unfortunately, this mode of transferring results is a slow process and sometimes the theoretically best algorithms perform poor in practice. Hence, practitioners often do not read research papers from the algorithms theory community. This causes a growing gap between theory and practice: Realistic hardware with its parallelism, memory hierarchies etc. is diverging from traditional machine models. This gap is also partially due to the fact that the research community working on algorithmic problems is fairly separated. One the one hand, there are ``hard core'' algorithms researchers that are focused mainly on theoretical work and rarely participate in conferences in application areas. On the other hand, researchers of application areas publish their work in conferences and journals of their respective field, and often do not visit theory conferences. In contrast to algorithm theory, algorithm engineering uses an innovation cycle where algorithm design based on realistic models, theoretical analysis, efficient implementation, and careful experimental evaluation using real-world inputs closes gaps between theory and practice and leads to improved application codes and reusable software libraries see (www.algorithm-engineering.de). This yields results that practitioners can rely on for their specific application.

Running Projects

Finished Projects