Sie sind hier

# Parameterized Algorithms for Finding a Collective Set of Items

Andrzej Kaczmarczyk (TU Berlin)

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.


Date
Speaker
Location
Language
12.12.2019
16:15
Andrzej Kaczmarczyk
TEL 512
English

Back to the research colloquium site.

To top