direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Elections with Few Candidates: Prices, Weights, and Covering Problems

Robert Bredereck (TU Berlin)

We show that a number of election-related problems with prices (such as, for example, bribery) are fixed-parameter tractable (in FPT) when parameterized by the number of candidates. For bribery, this resolves a nearly 10-year old family of open problems. Our results follow by a general technique that formulates voting problems as covering problems and extends the classic approach of using integer linear programming and the algorithm of Lenstra. In this context, our central result is that WEIGHTED SET MULTICOVER parameterized by the universe size is fixed-parameter tractable. Our approach is also applicable to weighted electoral control for Approval voting. We improve previously known XP-memberships to FPT-memberships. Our preliminary experiments on real-world-based data show the practical usefulness of our approach for instances with few candidates.

Joint work with Piotr Faliszewski, Rolf Niedermeier, Piotr Skowron, and Nimrod Talmon.

Date
Speaker
Location
Language
09.07.2015
16:15
Robert Bredereck
TEL 512
English

Back to the research colloquium site.

Zusatzinformationen / Extras