Parameterized Algorithmics for Voting Systems

• Applicant: Professor Dr. Rolf Niedermeier (†)
• Subject Area: Theoretical Computer Science
• Term: from 2009 to 2014
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 128081774

Many voting problems are NP-hard, hence there is no hope for polynomial-time solutions. Among such problems we find specific cases of winner determination or the optimization of lobbying in multiple referenda. However, voting problems typically carry natural parameterizations; for instance, obvious parameters are the number of candidates or the number of votes. Depending on the concrete application behind, each of these parameters may be small. The project PAWS targets at determining the influence of various parameterizations on the computational complexity of natural voting problems. The employed methods include complexity-theoretic techniques as well as implementation and empirical testing of newly developed algorithms.

• DFG Programme: Research Grants