Skowron and Faliszewski (2015) - Fully Proportional Representation with Approval Ballots: Approximating the MaxCover Problem with Bounded Frequencies in FPT Time

From Online-Partizipation
Jump to navigation Jump to search

P. K. Skowron and P. Faliszewski. Fully Proportional Representation with Approval Ballots: Approximating the MaxCover Problem with Bounded Frequencies in FPT Time. Proceedings of the 29th AAAI Conference on Artificial Intelligence, 2015.

Summary

The authors study the approval-based variant of Chamberlin-Courant multiwinner voting. They show equivalence to the budgeted maximum coverage problem, which is known to be NP-complete. Further they present FPT-approximations.

BibTeX

@inproceedings{sko-fal:c:aprrox-max-cover-bounded-frequencies-fpt,
 title={{F}ully {P}roportional {R}epresentation with {A}pproval {B}allots: {A}pproximating the {M}ax{C}over {P}roblem with {B}ounded {F}requencies in {FPT} {T}ime},
 author={Skowron, Piotr Krzysztof and Faliszewski, Piotr},
 booktitle={Proceedings of the 29th AAAI Conference on Artificial Intelligence},
 year={2015}
}