5 papers
A Multivariate Complexity Analysis of the Material Consumption Scheduling Problem
Matthias Bentert, Robert Bredereck, Péter Györgyi +2
The NP-hard MATERIAL CONSUMPTION SCHEDULING Problem and closely related problems have been thoroughly studied since the 1980's. Roughly speaking, the problem deals with minimizing…
Envy-Free Allocations Respecting Social Networks
Robert Bredereck, Andrzej Kaczmarczyk, Rolf Niedermeier
Finding an envy-free allocation of indivisible resources to agents is a central task in many multiagent systems. Often, non-trivial envy-free allocations do not exist, and, when th…
Line-Up Elections: Parallel Voting with Shared Candidate Pool
Niclas Boehmer, Robert Bredereck, Piotr Faliszewski +2
We introduce the model of line-up elections which captures parallel or sequential single-winner elections with a shared candidate pool. The goal of a line-up election is to find a…
Algorithms for Destructive Shift Bribery
Andrzej Kaczmarczyk, Piotr Faliszewski
We study the complexity of Destructive Shift Bribery. In this problem, we are given an election with a set of candidates and a set of voters (each ranking the candidates from the b…
On Coalitional Manipulation for Multiwinner Elections: Shortlisting
Robert Bredereck, Andrzej Kaczmarczyk, Rolf Niedermeier
Shortlisting of candidates--selecting a group of "best" candidates--is a special case of multiwinner elections. We provide the first in-depth study of the computational complexity…