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 at AAMAS 2025 19 Dec 2024
Our paper "Opinion Dynamics with Median Aggregation" (by Petra Berenbrink, Martin Hoefer, Marten Maack, Malin Rau, Dominik Schallmoser, Lisa Wilhelmi) was accepted as full paper at the 24th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2025), the international top conference in multi-agent systems.
New Paper at STACS 2025 13 Dec 2024
Our paper "Designing Exploration Contracts" (by Martin Hoefer, Conrad Schecker, Kevin Schewior) was accepted at the 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025), a leading conference in theoretical computer science.
Visitor 11 Dec 2024
Daniel Schmand is visiting our group Dec 11-13.
Welcome 1 Dec 2024
Sukanya Pandey joined our group as a postdoc. Welcome, Sukanya!
New Paper at SOFSEM 2025 12 Nov 2024
Treasure hunt problems are a variant of graph exploration problems, in which a ''searcher'' needs to find a hidden treasure that is located at a designated vertex in an unknown graph. In our paper ''The Complexity of Graph Exploration Games'' (by Janosch Fuchs, Christoph Grüne, Tom Janßen), we analyze the complexity of different variations of graph exploration and treasure hunt problems. These problems usually come as online problems. We assume that the searcher carries a map of an isomorphic copy of the graph for orientation. We show PSPACE-completeness for the problem of exploring the graph completely or finding the treasure. The paper has been accepted at the 50th International Conference of Current Trends in Theory and Practice of Computer Science (SOFSEM 2025).
New Paper in Mathematics of Operations Research 10 Nov 2024
The Nash social welfare, given by the product of agent valuations, is a popular objective when assigning indivisble goods to a set of agents. While it has desirable fairness properties, optimization is in general intractable. In our paper ''Maximizing Nash Social Welfare in 2-Value Instances: Delineating Tractability'' (by Hannaneh Akrami, Bhaskar Ray Chaudhury, Martin Hoefer, Kurt Mehlhorn, Marco Schmalhofer, Golnoosh Shahkarami, Giovanna Varricchio, Quentin Vermande, Ernest van Wijland) we examine the (in-)tractability in one of the most elementary scenarios, in which additive valuations are based on two non-negative integers p > q. Interestingly, if the ratio p/q (after reduction) is integral or half-integral, we obtain efficient algorithms to find an optimal solution. If p/q has denominator at least 3, the problem becomes intractable. The paper has been accepted for publication in Mathematics of Operations Research, a leading journal in operations research.