Szczegóły publikacji
Opis bibliograficzny
Near-tight algorithms for the Chamberlin-Courant and Thiele voting rules / Krzysztof SORNAT, Virginia Vassilevska Williams, Yinzhan Xu // W: IJCAI-22 [Dokument elektroniczny] : proceedings of the thirty-first International Joint Conference on Artificial Intelligence : Vienna, Austria, 23-29 July 2022 / ed. Luc De Raedt. — Wersja do Windows. — Dane tekstowe. — [USA] : International Joint Conferences on Artificial Intelligence, cop. 2022. — e-ISBN: 978-1-956792-00-3. — S. 482–488. — Wymagania systemowe: Adobe Reader. — Tryb dostępu: https://www.ijcai.org/proceedings/2022/0069.pdf [2022-10-27]. — Bibliogr. s. 487–488, Abstr.
Autorzy (3)
- AGHSornat Krzysztof
- Williams Virginia Vassilevska
- Xu Yinzhan
Dane bibliometryczne
| ID BaDAP | 143384 |
|---|---|
| Data dodania do BaDAP | 2022-11-09 |
| Rok publikacji | 2022 |
| Typ publikacji | materiały konferencyjne (aut.) |
| Otwarty dostęp |  |
| Konferencja | International Joint Conference on Artificial Intelligence 2022 |
Abstract
We present an almost optimal algorithm for the classic Chamberlin-Courant multiwinner voting rule (CC) on single-peaked preference profiles. Given n voters and m candidates, it runs in almost linear time in the input size improving the previous best O(nm2) time algorithm. We also study multiwinner voting rules on nearly single-peaked preference profiles in terms of the candidate-deletion operation. We show a polynomial-time algorithm for CC where a given candidate-deletion set D has logarithmic size. Actually, our algorithm runs in 2|D|· poly(n, m) time and the base of the power cannot be improved under the Strong Exponential Time Hypothesis. We also adapt these results to all non-constant Thiele rules which generalize CC with approval ballots. © 2022 International Joint Conferences on Artificial Intelligence. All rights reserved.
