Parameterized Algorithms for Finding a Collective Set of Items

Robert Bredereck, Piotr Faliszewski, Andrzej Kaczmarczyk, Dusan Knop, Rolf Niedermeier

AAAI 2020 pp. 1838-1845

doi:10.1609/AAAI.V34I02.5551 /aaai/2020/bredereck2020aaai-parameterized/

Abstract

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.

PDF AAAI Semantic Scholar

Cite

Text

Bredereck et al. "Parameterized Algorithms for Finding a Collective Set of Items." AAAI Conference on Artificial Intelligence, 2020. doi:10.1609/AAAI.V34I02.5551

Markdown

[Bredereck et al. "Parameterized Algorithms for Finding a Collective Set of Items." AAAI Conference on Artificial Intelligence, 2020.](https://mlanthology.org/aaai/2020/bredereck2020aaai-parameterized/) doi:10.1609/AAAI.V34I02.5551

BibTeX

@inproceedings{bredereck2020aaai-parameterized,
  title     = {{Parameterized Algorithms for Finding a Collective Set of Items}},
  author    = {Bredereck, Robert and Faliszewski, Piotr and Kaczmarczyk, Andrzej and Knop, Dusan and Niedermeier, Rolf},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year      = {2020},
  pages     = {1838-1845},
  doi       = {10.1609/AAAI.V34I02.5551},
  url       = {https://mlanthology.org/aaai/2020/bredereck2020aaai-parameterized/}
}