Parameterized Algorithms for Finding a Collective Set of Items

We extend the work of Skowron et al. (AIJ, 2016) by considering the parameterized complexity of the following problem. We are given a set of items and a set of agents, where each agent assigns an integer utility value to each item. The goal is to find a set of k items that these agents would collectively use. For each such collective set of items, each agent provides a score that can be described using an OWA (ordered weighted average) operator and we seek a set with the highest total score. We focus on the parameterization by the number of agents and we find numerous fixed-parameter tractability results (however, we also find some W[1]-hardness results). It turns out that most of our algorithms even apply to the setting where each agent has an integer weight.

Authors

• Robert Bredereck TU Clausthal, Institut für Informatik
• Piotr Faliszewski AGH University of Krakow
• Andrzej Kaczmarczyk Czech Technical University of Prague
• Dušan Knop Czech Technical University in Prague
• Rolf Niedermeier

Keywords

No keywords are indexed for this paper.