Research

Combinatorial Optimization is a branch of Mathematical Optimization with a vast number of applications. Be it the navigation system in your car, the software used to create timetables for high schools, or decision support systems in production and logistic environments, you can be almost certain that modern Combinatorial Optimization techniques are employed.

Technically speaking, Combinatorial Optimization is concerned with finding an optimal or close to optimal solution among a finite collection of possibilities. The finite set of possible solutions is typically described through mathematical structures, like graphs, matroids or independence systems. The focus in Combinatorial Optimization lies on efficient algorithms which, more formally, means algorithms with a running time bounded by a polynomial in the input size. Therefore, two of the arguably most prominent questions in Combinatorial Optimization are:

• How quickly can one find a single (or all) optimal solution(s) of a given problem?
• When dealing with a problem where, due to complexity-theoretic reasons, it is unlikely that an optimal solution can be found efficiently: What is the best solution quality that an efficient algorithm can guarantee?

Over the last decades, Combinatorial Optimization has grown into a very mature field with strong links to various other disciplines like discrete mathematics (graph theory, combinatorics, ...), computer science (data structures, complexity theory, ...), probability theory, continuous optimization, and many application areas. Advances in modern Combinatorial Optimization thus often happen through clever combinations of ideas from several fields.

In our group, we have expertise and research interests in a broad spectrum of Combinatorial Optimization problems and its applications. A particular focus is put on polyhedral techniques, which have proven to be a unifying and coherent approach to a wide set of Combinatorial Optimization problems.

Algorithmic research on discrete mathematical structures like matroids and submodular functions, and their applications

At the heart of efficient combinatorial algorithms often lies the identification and exploitation of a discrete mathematical structure that is hidden in the problem. A thorough understanding of discrete structures and their algorithmic implications is therefore of central importance in Combinatorial Optimization. Two very general discrete structures with strong algorithmic properties are matroids and submodular functions, which can be found in a surprising and steadily growing number of applications.

Numerous results have already been discovered for such algorithmically important mathematical structures. However, partially due to upcoming research areas, like online algorithms and submodular function maximization, many new open questions arose in the context of classical discrete structures. We believe that substantial progress in such emerging areas is tightly linked to deeper mathematical insights.

We therefore have a strong interest in the study of discrete structures, in particular (poly-)matroids and submodular functions, and their various applications. Our interest in this context covers a wide range of problems, including submodular function maximization, network coding, online algorithms, constrained spanning trees, Steiner Tree relaxations, multiobjective optimization, and matroid secretary problems.

Network optimization: robustness and network design

Network optimization is a classic research focus in Combinatorial Optimization, and an important reason for the widespread use of Combinatorial Optimization in various application areas. Network optimization has many facets, and we are interested in a diverse set of network optimization problems. In particular, we study network design problems (like generalized spanning tree problems, the Steiner Tree problem, design of failure-resilient networks, ...), routing and coding problems (automatically-guided vehicles, wireless coding models, ...) and many more.

Furthermore, we have a particular interest in problems related to network robustness. Problems in network robustness account for the fact that many real-world networks are prone to failures of some of their components and that network data used in network optimization problems may be inaccurate.

Interdisciplinary projects

Combinatorial Optimization approaches are crucial tools in many of our interdisciplinary projects and industrial collaborations. Further information on these projects can be found on the industrial collaborations site of the Zenklusen group.