Podstawy Informatyki

Organizers: Marek Zaionc
Usual time and place: środa, 12:15-14:00, sala 0086
event-date: 20.10.2010
Speaker: Piotr Faliszewski (AGH)
Title of the talk: A 2-Approximation Algorithm for a Candidate Promotion Problem
Abstract:

We are given an election E=(C,V), where C is a set of alternatives, and V is a collection of voters, and a preferred alternative p. Each voter is represented by a linear order over C. As part of a political campaign, we have the ability (at some cost) to shift p forward in some of the votes. In the shift-bribery problem we ask for the minimal cost of shifts that ensure our candidate's victory. We show that this problem is NP-complete (for Borda winner determination rule; an example of so-called scoring rules) and give a 2-approximation algorithm that works for all scoring rules, even if the votes are weighted.