On Approximating Optimal Weighted Lobbying, and Frequency of Correctness Versus Average-Case Polynomial Time

Gábor Erdélyi, Lane A. Hemaspaandra, Jörg Rothe, Holger Spakowski

Abstract

We investigate issues regarding two hard problems related to voting, the optimal weighted lobbying problem and the winner problem for Dodgson elections. Regarding the former, Christian et al. [2] showed that optimal lobbying is intractable in the sense of parameterized complexity. We provide an efficient greedy algorithm that achieves a logarithmic approximation ratio for this problem and even for a more general variant—optimal weighted lobbying. We prove that essentially no better approximation ratio than ours can be proven for this greedy algorithm.
BibTeX
@inproceedings{erdelyi2007approximating,
  author = {Gábor Erdélyi and Lane A. Hemaspaandra and Jörg Rothe and Holger Spakowski},
  title = {{On Approximating Optimal Weighted Lobbying, and Frequency of Correctness Versus Average-Case Polynomial Time}},
  booktitle = {FCT},
  year = {2007},
  doi = {10.1007/978-3-540-74240-1\_26},
}

Loading related content...

Figure