Szczegóły publikacji
Opis bibliograficzny
Approximation and hardness of Shift-Bribery / Piotr FALISZEWSKI, Pasin Manurangsi, Krzysztof Sornat // Artificial Intelligence ; ISSN 0004-3702. — 2021 — vol. 298 art. no. 103520, s. 1–26. — Bibliogr. s. 25–26, Abstr. — Publikacja dostępna online od: 2021-04-30
Autorzy (3)
- AGHFaliszewski Piotr
- Manurangsi Pasin
- Sornat Krzysztof
Słowa kluczowe
Dane bibliometryczne
| ID BaDAP | 134526 |
|---|---|
| Data dodania do BaDAP | 2021-06-14 |
| Tekst źródłowy | URL |
| DOI | 10.1016/j.artint.2021.103520 |
| Rok publikacji | 2021 |
| Typ publikacji | artykuł w czasopiśmie |
| Otwarty dostęp |  |
| Czasopismo/seria | 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 Shift-Bribery problem for the case of positional scoring rules, and for the Copeland rule we show strong inapproximability results.
