TU Berlin

Algorithmics and Computational Complexity Research GroupTalk 12.12.2019


Page Content

to Navigation

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.


Andrzej Kaczmarczyk
TEL 512

Back to the research colloquium site.

To top


Quick Access

Schnellnavigation zur Seite über Nummerneingabe