Szczegóły publikacji
Opis bibliograficzny
Elections with few candidates: prices, weights, and covering problems / Robert Bredereck, Piotr FALISZEWSKI, Rolf Niedermeier, Piotr Skowron, Nimrod Talmon // W: Algorithmic decision theory : 4th international conference : ADT 2015 : Lexington, USA, September 27–30 2015 : proceedings / ed. Toby Walsh. — Switzerland : Springer International Publishing, cop. 2015. — (Lecture Notes in Computer Science ; ISSN 0302-9743 ; 9346. Lecture Notes in Artificial Intelligence). — ISBN: 978-3-319-23113-6; e-ISBN: 978-3-319-23114-3. — S. 414–431. — Bibliogr. s. 430–431, Abstr.
Autorzy (5)
- Bredereck Robert
- AGHFaliszewski Piotr
- Niedermeier Rolf
- Skowron Piotr
- Talmon Nimrod
Dane bibliometryczne
| ID BaDAP | 91584 |
|---|---|
| Data dodania do BaDAP | 2015-10-08 |
| DOI | 10.1007/978-3-319-23114-3_25 |
| Rok publikacji | 2015 |
| Typ publikacji | materiały konferencyjne (aut.) |
| Otwarty dostęp |  |
| Konferencja | 4th International Conference on Algorithmic Decision Theory |
| Czasopismo/seria | Lecture Notes in Computer Science |
Abstract
We show that a number of election-related problems with prices (such as, for example, bribery) are fixed-parameter tractable (in FPT) when parameterized by the number of candidates. For bribery, this resolves a nearly 10-year old family of open problems. Our results follow by a general technique that formulates voting problems as covering problems and extends the classic approach of using integer linear programming and the algorithm of Lenstra [19]. In this context, our central result is that WEIGHTED SET MULTICOVER parameterized by the universe size is fixed-parameter tractable. Our approach is also applicable to weighted electoral control for Approval voting. We improve previously known XP-memberships to FPT-memberships. Our preliminary experiments on real-world-based data show the practical usefulness of our approach for instances with few candidates.
