Contact
Algorithms and Complexity
Computer Science 1
RWTH Aachen University
Ahornstrasse 55
D-52074 Aachen
Secretary Office:
Erika Schlebusch
Informatikzentrum, E1
Room 4023
Tel.: +49 (0) 241 80-21101
New Paper in Mathematical Programming 8 Aug 2026
In our new paper "Online Proportional Apportionment" (by Javier Cembrano, Jose Correa, Svenja Griesbach, Victor Verdugo) we analyze strategies to iteratively assign parliament seats to parties based on voter shares. We consider a challenging online scenario, where in each round a certain share of the votes become known and a number of seats have to be assigned, ensuring that each party receives a fractional share rounded up or down, and that the cumulative numbers of seats remain representative to the total votes up to that time. Our results reveal an interesting dichotomy. For 3 parties, there are efficient (randomized) algorithms that allow to satisfy global quota and individual proportional share constraints. For more than 3 parties, the corresponding guarantees are in general impossible to obtain. The paper has been accepted for publication in Mathematical Programming, a leading journal in applied mathematics and operations research.
New Paper in Mathematics of Operations Research 2 Aug 2026
In our new paper "Public Signals in Affine Network Congestion Games with Uncertain Free-Flow Times" (by Svenja Griesbach, Martin Hoefer, Max Klimm, Tim Koglin) we study a natural recommendation problem in traffic networks with rational participants. A benevolent traffic service has information about the true status of the network and sends route recommendations to users who are partially unaware of the network status. Each user can adhere to the recommended route or choose to deviate. Our algorithms provide persuasive recommendation schemes, i.e., given the expected status of the network, each user finds it in their interest to follow the recommended route. We show structural characterizations when full information revelation represents optimal recommendations. Our algorithms use the informational surplus of the traffic service to minimize total delay in the resulting traffic flows. The paper has been accepted for publication in Mathematics of Operations Research, a leading journal in operations research.
Dissertation Award 06 Jul 2025
Svenja Griesbach is receiving the 2026 dissertation award by the Berliner Wissenschaftliche Gesellschaft and the Erhard Höpfner Stiftung. Congratulations, Svenja!
New Paper at ESA 2026 26 Jun 2026
Our paper "The Complexity of Stackelberg Pricing Games" (by Christoph Grüne, Dorothee Henke, Eva Rotenberg, Lasse Wulf) was accepted at the 34th European Symposium on Algorithms (ESA 2026), the European top-conference in design and analysis of algorithms.
New Paper at APPROX 2026 26 Jun 2026
Our paper "Approximation Algorithms for Discounted Graph Search with Norm Objectives" (by Svenja Griesbach, Felix Hommelsheim, Max Klimm) was accepted at the 28th International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2026).
New Paper at EC 2026 19 May 2026
Our paper "Carbon Pricing in Traffic Networks" (by Svenja Griesbach, Tobias Harks, Max Klimm, Michael Markl, Philipp Warode) was accepted at the 27th Conference on Economics and Computation (EC 2026), the international top conference at the intersection of economics and computer science.
Visitor 20 May 2026
Frederik Mallmann-Trenn is visiting our group May 26-29.
Artikel in der Süddeutschen Zeitung 01 Apr 2026
Im Artikel "So ist es gerecht. Oder?" berichtet die Süddeutsche Zeitung über grundlegende Resultate zu Fair Division und erwähnt dabei auch unsere Forschungen zu Envy-Freeness.