Towards Understanding the Role of Structure in Combinatorial Optimisation

17^th April 2026, 13:30 ALT
Joachim Spoerhase

Abstract

The task of determining an optimal solution to a given problem (combinatorial optimisation problem) is ubiquitous in computer science, mathematics, and many areas of application. For example, network design problems such as the well-known Traveling Salesman or Steiner tree problems arise naturally in logistics, computer networks, and operations research. Another example are clustering problems, which aim to categorise a set of objects into groups (clusters) of similar objects, and and are widely applied in data analysis, machine learning, location planning, or social choice.  From an algorithms and complexity point of view, the ultimate goal is to design algorithms for combinatorial optimisation problems that achieve a provably best-possible trade-off between the quality of the solution computed by the algorithm and the required computational resources such as running time. For various basic (nearly unstructured) types of problems (such as MaxCSP or covering problems)  provably best-possible algorithms are  known from the literature and can be obtained in an entirely systematic way. On the other hand, existing results for more structured problems (such as clustering or network design) are much more scattered and ad-hoc. In this talk, I give an overview over some of my work on such structured problems and related research directions. A first such direction is to design unified algorithms for problems arising in clustering, network design, packing, and geometry. A second direction aims to systematically leverage the structural properties of more realistic inputs to these problems in order to obtain stronger guarantees on quality and computational resources. I discuss some of my previous results, which can be seen as first steps in these directions.