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 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 are usually modeled as online problems. We additionally assume the searcher to carry a map of a isomorphic copy of the graph for orientation. We show PSPACE-completeness for answering the question whether the searcher is able to explore the graph completely or to find the treasure. The paper has been accepted at the 50th International Conference of Current Trends in Theory and Practice of Computer Science.
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 often computationally 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.
Welcome 1 October 2024
Finn Seesemann joined our group as a PhD student. Welcome, Finn!
New Paper in ACM Transactions on Economics and Computation 23 Aug 2024
In our paper ''Algorithmic Persuasion with Evidence'' (by Martin Hoefer, Pasin Manurangsi, Alexandros Psomas) we examine the computational complexity of recommendation problems with evidence. This model serves to capture recommendation scenarios, in which a sender (e.g., say, a prosecuter) strives to convince a receiver (judge) to take a certain decision (convict a defendant) - while the receiver would like to take a correct decision (a fair judgement). To do so, the sender, who knows the true state of the world, can present concrete evidence to the receiver, based on which the receiver forms a belief about the state and takes a decision accordingly. In our paper, we provide efficient algorithms for computing an equilibrium in this signaling game. We also give algorithms to compute (near-)optimal solutions and show tight approximation hardness for the bi-level optimization problems that emerge when one of the agents has commitment power. The paper has been accepted for publication in ACM Transactions on Economics and Computation.
Welcome 1 August 2024
Rilind Sahitaj joined our group as a PhD student. Welcome, Rilind!
New Paper at WAOA 2024 31 July 2024
Our paper ''Approximating δ-Covering'' (by Tim Hartmann, Tom Janßen) was accepted at the 22nd Workshop on Approximation and Online Algorithms (WAOA 2024).
Website Launch 26 July 2024
Our new website is online.
New Paper in Artificial Intelligence 10 June 2024
In our paper ''Delegated Online Search'' (by Pirmin Braun, Niklas Hahn, Martin Hoefer, Conrad Schecker) we study a natural delegation problem, in which a prinicipal (say, a company) outsources the search for a good alternative to an agent (say, a head hunter searching for a job candidate, or a financial agent scanning investment options). The principal specifies criteria for acceptable options in advance (say, qualifications for hiring, or properties of the investment). The agent searches sequentially through the (initally unknown) options in an online fashion and chooses one that is acceptable to the principal and most preferred by the agent. Our contribution is to design efficient algorithms for the principal. Our algorithms set acceptance criteria in order to obtain a good alternative, even though the preferences of principal and agent might be misaligned. The paper has been accepted for publication in Artificial Intelligence, the international top-journal in AI.
A New Beginning 1 June 2024
After more than 7 very successful years at Goethe University, our group will be moving to RWTH Aachen University over the summer. We are excited about the new opportunities and thank everyone for the great time in Frankfurt.