- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- BIRS Workshop Lecture Videos /
- FPT approximation schemes for Shift Bribery
Open Collections
BIRS Workshop Lecture Videos
BIRS Workshop Lecture Videos
FPT approximation schemes for Shift Bribery Nichterlein, André
Description
In the Shift Bribery problem, we are given an election (based on preference orders), a preferred candidate p, and a budget. The goal is to ensure that p wins by shifting p higher in some voters' preference orders. However, each such shift request comes at a price (depending on the voter and on the extent of the shift) and we have to minimize the overall costs. In this talk, we show FPT approximation schemes for the Copeland voting rule (the winner is the candidate winning the most head-to-head competitions) with respect to each of the parameters number of voters and number of candidates.This is joint work with Robert Bredereck, Jiehua Chen, Piotr Faliszewski, and Rolf Niedermeier.
Item Metadata
Title |
FPT approximation schemes for Shift Bribery
|
Creator | |
Publisher |
Banff International Research Station for Mathematical Innovation and Discovery
|
Date Issued |
2015-11-30T11:12
|
Description |
In the Shift Bribery problem, we are given an election (based on preference orders), a preferred
candidate p, and a budget. The goal is to ensure that p wins by shifting p higher in some voters' preference
orders. However, each such shift request comes at a price (depending on the voter and on the extent of the
shift) and we have to minimize the overall costs. In this talk, we show FPT approximation schemes for
the Copeland voting rule (the winner is the candidate winning the most head-to-head competitions) with
respect to each of the parameters number of voters and number of candidates.This is joint work with Robert Bredereck, Jiehua Chen, Piotr Faliszewski, and Rolf Niedermeier.
|
Extent |
30 minutes
|
Subject | |
Type | |
File Format |
video/mp4
|
Language |
eng
|
Notes |
Author affiliation: Technische Universität Berlin
|
Series | |
Date Available |
2016-05-31
|
Provider |
Vancouver : University of British Columbia Library
|
Rights |
Attribution-NonCommercial-NoDerivatives 4.0 International
|
DOI |
10.14288/1.0303471
|
URI | |
Affiliation | |
Peer Review Status |
Unreviewed
|
Scholarly Level |
Postdoctoral
|
Rights URI | |
Aggregated Source Repository |
DSpace
|
Item Media
Item Citations and Data
Rights
Attribution-NonCommercial-NoDerivatives 4.0 International