Please use this identifier to cite or link to this item: doi:10.22028/D291-40179
Title: Parameterized complexity of multiwinner determination: more effort towards fixed-parameter tractability
Author(s): Yang, Yongjie
Wang, Jianxin
Language: English
Title: Autonomous Agents and Multi-Agent Systems
Volume: 37
Issue: 2
Publisher/Platform: Springer Nature
Year of Publication: 2023
Free key words: Multiwinner voting
Fixed-parameter tractability
Minimax approval voting
Proportional approval voting
Chamberlin–Courant’s approval voting
W[1]- hard
DDC notations: 330 Economics
Publikation type: Journal Article
Abstract: We study the parameterized complexity of winner determination problems for three prevalent k-committee selection rules, namely the minimax approval voting (MAV), the proportional approval voting (PAV), and the Chamberlin–Courant’s approval voting (CCAV). It is known that these problems are computationally hard. Although they have been studied from the parameterized complexity point of view with respect to several natural parameters, many of them turned out to be W[1]-hard or W[2]-hard. Aiming at obtaining plentiful fxed-parameter algorithms, we revisit these problems by considering more natural single parameters, combined parameters, and structural parameters.
DOI of the first publication: 10.1007/s10458-023-09610-z
URL of the first publication:
Link to this record: urn:nbn:de:bsz:291--ds-401791
ISSN: 1573-7454
Date of registration: 24-Jul-2023
Faculty: HW - Fakultät für Empirische Humanwissenschaften und Wirtschaftswissenschaft
Department: HW - Wirtschaftswissenschaft
Professorship: HW - Keiner Professur zugeordnet
Collections:SciDok - Der Wissenschaftsserver der Universität des Saarlandes

Files for this record:
File Description SizeFormat 
s10458-023-09610-z.pdf2,26 MBAdobe PDFView/Open

This item is licensed under a Creative Commons License Creative Commons