Szczegóły publikacji
Opis bibliograficzny
Parameterized algorithms for finding a collective set of items / Robert Bredereck, Piotr FALISZEWSKI, Andrzej Kaczmarczyk, Dušan Knop, Rolf Niedermeier // W: AAAI-20 / IAAI-20 / EAAI-20 proceedings : thirty-fourth AAAI conference on Artificial Intelligence, thirty-second conference on Innovative Applications of Artificial Intelligence, the tenth symposium on Educational Advances in Artificial Intelligence : February 7–12th, 2020, New York. — Palo Alto : AAAI Press, cop. 2020. — (Proceedings of the ... AAAI Conference on Artificial Intelligence ; ISSN 2159-5399 ; vol 34 no. 02: AAAI-20 Technical Tracks 2). — ISBN: 978-1-57735-835-0. — S. 1838–1845. — Bibliogr. s. 1845, Abstr.
Autorzy (5)
- Bredereck Robert
- AGHFaliszewski Piotr
- Kaczmarczyk Andrzej
- Knop Dušan
- Niedermeier Rolf
Dane bibliometryczne
| ID BaDAP | 130852 |
|---|---|
| Data dodania do BaDAP | 2020-11-04 |
| Tekst źródłowy | URL |
| DOI | 10.1609/aaai.v34i02.5551 |
| Rok publikacji | 2020 |
| Typ publikacji | materiały konferencyjne (aut.) |
| Otwarty dostęp |  |
| Konferencje | National Conference of the American Association for Artificial Intelligence 2020, Innovative Applications in AI 2020 |
| Czasopismo/seria | Proceedings of the ... AAAI Conference on Artificial Intelligence |
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.
