direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Optimal Lobbying Revisited

Jiehua Chen (TU Berlin)

Given a multi-issue election W in {0,1}^{n * m}, a non-negative
integer k < n, and a desired outcome vector x in {0,1}^m, we study the
parameterized complexity of {\sc Optimal Lobbying}: whether it is
possible to lobby at most k voters, such that the outcome of the lobbied
election equals x . In this talk, we will show that Optimal Lobbying is
fixed-parameter tractable with respect to the parameter "number m of
issues", but NP-hard for the case that x = 1^m and each row of W
contains at most three ones.

01.12.2011 16:15
Jiehua Chen
FR 6510

Back to the research colloquium site.

Zusatzinformationen / Extras