Podstawy Informatyki

Prowadzący: Marek Zaionc
Zwyczajowy czas i miejsce: środa, 12:15-14:00, sala 0086
Termin: 20.10.2010
Referent: Piotr Faliszewski (AGH)
Tytuł referatu: A 2-Approximation Algorithm for a Candidate Promotion Problem
Streszczenie:

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.