Szczegóły publikacji
Opis bibliograficzny
Approximation and hardness of Shift-Bribery / Piotr FALISZEWSKI, Pasin Manurangsi, Krzysztof Sornat // W: AAAI-19/IAAI-19/EAAI-19 [Dokument elektroniczny] : thirty-third AAAI conference on Artificial Intelligence, thirty-first conference on Innovative Applications of Artificial Intelligence, the ninth symposium on Educational Advances in Artificial Intelligence : January 27–February 1, 2019, Honolulu, Hawaii, USA : proceedings. — Wersja do Windows. — Dane tekstowe. — Palo Alto : Association for the Advancement of Artificial Intelligence AAAI, cop. 2019. — (Proceedings of the ... AAAI Conference on Artificial Intelligence ; ISSN 2159-5399). — ISBN: 978-1-57735-809-1. — S. 1901–1908. — Wymagania systemowe: Adobe Reader. — Tryb dostępu: https://aaai.org/ojs/index.php/AAAI/article/view/4016/3894 [2019-10-10]. — Bibliogr. s. 1908, Abstr. — Publikacja dostępna online od: 2019-07-23
Autorzy (3)
- AGHFaliszewski Piotr
- Manurangsi Pasin
- Sornat Krzysztof
Dane bibliometryczne
| ID BaDAP | 125193 |
|---|---|
| Data dodania do BaDAP | 2019-12-13 |
| Rok publikacji | 2019 |
| Typ publikacji | materiały konferencyjne (aut.) |
| Otwarty dostęp |  |
| Konferencja | National Conference of the American Association for Artificial Intelligence 2019 |
| Czasopismo/seria | Proceedings of the ... AAAI Conference on Artificial Intelligence |
Abstract
In the SHIFT-BRIBERY problem we are given an election, a preferred candidate, and the costs of shifting this preferred candidate up the voters' preference orders. The goal is to find such a set of shifts that ensures that the preferred candidate wins the election. We give the first polynomial-time approximation scheme for the case of positional scoring rules, and for the Copeland rule we show strong inapproximability results.
