PTAS for Minimax Approval Voting
Jaros Law Byrka, Krzysztof Sornat · 2016
Abstract. We consider Approval Voting systems where each voter de-cides on a subset of candidates he/she approves. We focus on the opti-mization 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 Carragia-nis 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. 1