Department of Computer Science | Institute of Theoretical Computer Science
The goal of the project is to find, study, and algorithmically exploit combinatorial models for certain discrete geometric optimization problems. Our main motivation is to enhance our understanding of the combinatorics behind linear programming and related---mostly geometric---optimization problems, improve on the performance guarantees of existing algorithms, and possibly discover novel, more efficient approaches. Classical such models are matroidsoriented matroids and submodular functions.
Within the last ten years, the concept of LP-type problems has become a recognized combinatorial model for linear programming and many other important geometric optimization problems. For many problems in the class, the currently best (or even optimal) combinatorial algorithm is an algorithm for general LP-type problems.
In the last couple of years new exciting combinatorial models for geometric optimization problems have emerged, such as unique sink orientations of cubes and strong LP-type problems. Just like LP-type problems ten years ago, these new combinatorial abstractions had immediate consequences; they provide the only available algorithms for certain linear complementarity problems with nontrivial running time guarantees.
Within this new project, we plan to explore unique sink orientations, strong LP-type problems, their relations to each other and to other known combinatorial models, as well as algorithms for problems fitting into the respective models.
The official ECG page contains more information about this project.
These independent developments share an important feature: they do not only apply to polytopes and Linear Programming but to a more general, `abstract' setting - the setting of LP-type problems. This success, made possible by taking an `abstract look' that goes beyond the concrete problem, subsequently led to many work on LP-type problems and other related frameworks.
The proposed project aims at deepening the understanding of these frameworks and its interplay with concrete problems. Here, the abstraction is not a goal in itself but a means to understand which properties of optimization problems are crucial for an efficient treatment, and which role randomization plays in the algorithms. The idea is to treat combinatorial questions on a combinatorial level, abstracting from actual coordinates and other representation issues. The ultimate goal is to turn the insights obtained into new upper and lower bounds for the combinatorial complexity of concrete optimization problems like Linear Programming.
My part of the project, carried out together with my PhD student Sven Schönherr dealt with geometric optimization software. The major deliverable is a quadratic programming solver tuned for applications in computational geometry, see the PhD thesis of Sven Schönherr.