MIMA - Combinatorial optimisation: hard, easy, efficient, fair?

by Eranda Dragoti-Cela (TU Graz)

Tuesday 12 May 2026, 11:45 → 12:45 Europe/Vienna

Seminarraum AE06 (Erdgeschoss) (Technische Universität Graz)

The talk will be held either in English or in German according to the audience. 

English

Combinatorial optimization lies at the intersection of mathematical beauty and computational necessity. 
At its core, it asks a simple question: how can we select the "best" subset or arrangement from a finite, yet astronomically large, set of possibilities? 

In classical models, we typically optimize a single aggregated objective, such as finding the shortest route for a delivery truck or themost economical way to connect a network.A central theme in this field is the distinction between problems that are computationally tractable and those that are computationally hard. While "easy" problems like Minimum Spanning Trees allow for fast, polynomial-time algorithms, "hard" problems like the travelling salesperson problem become exponentially difficult as they grow. A key area of our research involves identifying specific structural properties of the input that can render these hard problems tractable.

The mathematical definition of an "optimal" solution often shifts when we consider the individual subjects involved. A solution that is mathematically optimal for the group can create large discrepancies in utility for individuals, leading to outcomes that are perceived as undesirable or fundamentally unfair. The search for the "best" solution is expanded to include fairness as a vital second objective. We investigate how to incorporate various fairness measures, such as egalitarian equity or envy-freeness, without losing the computational tractability that makes a solution useful in practice. 

 

Deutsch

Kombinatorische Optimierung: schwer, einfach, effizient, fair?

Die kombinatorische Optimierung liegt an der Schnittstelle zwischen mathematischer Schönheit und computergestützter Notwendigkeit. Im Kern befasst sie sich mit einer einfachen Frage: Wie können wir die „beste“ Teilmenge oder Anordnung aus einer endlichen, aber astronomisch großen Menge von Möglichkeiten auswählen? 

In klassischen Modellen optimieren wir in der Regel eine einzelne aggregierte Zielfunktion, wie etwa die Suche nach der kürzesten Route für einen Lieferwagen oder die wirtschaftlichste Art, ein Netzwerk zu verbinden. Ein zentrales Thema in diesem Bereich ist die Unterscheidung zwischen Problemen, die rechnerisch handhabbar (tractable) sind, und solchen, die rechnerisch schwer (hard) sind. Während „einfache“ Probleme wie minimale Spannbäume schnelle Algorithmen mit polynomieller Laufzeit ermöglichen, werden „harte“ Probleme wie das Rundreiseproblem mit zunehmender Größe exponentiell schwierig zu lösen. Ein Schwerpunkt unserer Forschung liegt darin, spezifische Struktureigenschaften der Eingabedaten zu identifizieren, die diese komplexen Landschaften vereinfachen und ansonsten schwere Probleme handhabbar machen können.

 

Die mathematische Definition einer „optimalen“ Lösung verschiebt sich jedoch oft, wenn wir die beteiligten Individuen berücksichtigen. Eine Lösung, die für die Gruppe optimal ist, kann für einzelne Akteure große Nutzenunterschiede (utility discrepancies) erzeugen, was zu Ergebnissen führt, die als unerwünscht oder grundlegend unfair empfunden werden.Diese Erkenntnis erweitert die  Suche nach der „besten“ Lösung um die Fairness als ein entscheidendes zweites Ziel. Wir  untersuchen, wie verschiedene Fairnessmaße, wie etwa egalitäre Gerechtigkeit oder Neidfreiheit (envy-freeness), einbezogen werden können, ohne die rechnerische Handhabbarkeit zu verlieren, die eine Lösung in der Praxis erst nutzbar macht.