Szczegóły publikacji
Opis bibliograficzny
Achieving fully proportional representation by clustering voters / Piotr FALISZEWSKI, Arkadii Slinko, Kolja Stahl, Nimrod Talmon // Journal of Heuristics ; ISSN 1381-1231. — 2018 — vol. 24 iss. 5, s. 725–756. — Bibliogr. s. 755–756, Abstr. — Publikacja dostępna online od: 2018-05-19
Autorzy (4)
- AGHFaliszewski Piotr
- Slinko Arkadii
- Stahl Kolja
- Talmon Nimrod
Słowa kluczowe
Dane bibliometryczne
| ID BaDAP | 117141 |
|---|---|
| Data dodania do BaDAP | 2018-10-12 |
| Tekst źródłowy | URL |
| DOI | 10.1007/s10732-018-9376-y |
| Rok publikacji | 2018 |
| Typ publikacji | artykuł w czasopiśmie |
| Otwarty dostęp |  |
| Czasopismo/seria | Journal of Heuristics |
Abstract
Both the Chamberlin–Courant and Monroe rules are voting rules that solve the problem of fully proportional representation: given a set of candidates and a set of voters, they select committees of candidates whose members represent the voters so that the voters’ total dissatisfaction is minimized. These two rules suffer from a common disadvantage, namely being computationally intractable. As both the Chamberlin–Courant and Monroe rules, explicitly or implicitly, partition voters so that the voters in each part share the same representative, they can be seen as clustering algorithms. This suggests studying approximation algorithms for these voting rules by means of cluster analysis, which is the subject of this paper. Using ideas from cluster analysis we develop several approximation algorithms for the Chamberlin–Courant and Monroe rules and experimentally analyze their performance. We find that our algorithms are computationally efficient and, in many cases, are able to provide solutions which are very close to optimal.
