Multiwinner elections and facility location problems: approximation and FPT algorithms.
Krzysztof Sornat (University of Wrocław)
In multiwinner elections we want to choose k winners that they somehow represents voters. In facility location problems we want to open k facilities that they somehow serve clients. Voters has dissatisfaction from choosing particular candidate. Clients has cost of being served by particular facility. These two worlds looks the same!
I will show examples of voting rules and facility location type of problems that are closely related. Then I will focus on approximation and parameterized algorithms for such problems. I will present examples how algorithmic paradigms and techniques for facility location can be adapted/generalized for multiwinner elections and I will introduce new facility location type of problems with nice motivation from social choice theory.
During my presentation I will be talking about the following techniques: independent rounding of a linear program solution, dependent rounding with negative association property, parameterized approximation scheme, ETH lower bounds, Charikar-Li clustering for k-median, and problems: Minimax Approval Voting, Closest String, k-center, k-median, Ordered k-median, Harmonic k-median, Proportional Approval Voting.
The talk is based on:
J. Byrka, K. Sornat. PTAS for Minimax Approval Voting. WINE 2014.
M. Cygan, Ł. Kowalik, A. Socała, K. Sornat. Approximation and Parameterized Complexity of Minimax Approval Voting. AAAI 2017.
J. Byrka, P. Skowron, K. Sornat. Proportional Approval Voting, Harmonic k-median, and Negative Association. CoRR, abs/1704.02183, 2017.
J. Byrka, K. Sornat, J. Spoerhase. Constant-Factor Approximation for Ordered k-Median. CoRR, abs/1711.01972, 2017.
Back to the research colloquium site.