Miniworkshop on 03.03.2016

On 03.03.2016 as a part of our Foundation for Polish Science Algorithmic Miniworkshop series we will have a seminar by Krzysztof Sormat. He will give a talk on his recent result on “PTAS for Minimax Approval Voting”. The abstract is given below.

We plan to have a group discussion and joint lunch after his talk.

Abstract: J. Byrka, K. Sornat. PTAS for Minimax Approval Voting. WINE 2014.

http://arxiv.org/abs/1407.7216

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.