27 listopada 2014 12:15
[Seminarium ZOK]. Krzysztof Sornat: PTAS for Minimax Approval Voting
Czwartek, 12:15, sala 310.
Abstract. We consider Approval Voting systems where each voter decides on a subset to candidates he/she approves. We focus on the optimization problem of finding the committee of fixed size k minimizing the maximal Hamming distance from a vote. In this paper we give a PTAS for this problem and hence resolve the open question raised by Carragianis et al. [AAAI'10]. The result is obtained by adapting the techniques developed by Li et al. [JACM'02] originally used for the less constrained Closest String problem. The technique relies on extracting information and structural properties of constant size subsets of votes.
Joint work with Jarosław Byrka from WINE 2014.