We study the computational complexity of committee selection problem for several approval-based voting rules in the presence of outliers. Our first result shows that outlier consideration makes committee selection problem intractable for approval, net approval, and minisum approval voting rules. We then study parameterized complexity of this problem with five natural parameters, namely the target score, the size of the committee (and its dual parameter, the number of candidates outside the committee), the number of outliers (and its dual parameter, the number of non-outliers). For net approval and minisum approval voting rules, we provide a dichotomous result, resolving the parameterized complexity of this problem for all subsets of five natural parameters considered (by showing either FPT or W[1]-hardness for all subsets of parameters). For the approval voting rule, we resolve the parameterized complexity of this problem for all subsets of parameters except one. We also study approximation algorithms for this problem. We show that there does not exist any alpha(.) factor approximation algorithm for approval and net approval voting rules, for any computable function alpha(.), unless P=NP. For the minisum voting rule, we provide a pseudopolynomial (1+eps) factor approximation algorithm.
We consider Approval Voting systems where each voter decides on a subset of 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 [AAAI’10]. The result is obtained by adapting the techniques developed by [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. In this work, we initiate a detailed study of the parameterized complexity of Minimax Approval Voting. We demonstrate that the problem is W[2]-hard when parameterized by the size of the committee to be chosen, but does admit a FPT algorithm when parameterized by the number of strings that is more efficient than the previous ILP-based approaches for the problem. We also consider several combinations of parameters and provide a detailed landscape of the parameterized and kernelization complexity of the problem. We also study the version of the problem where we permit outliers, that is, where the chosen committee is required to satisfy a large number of voters (instead of all of them). In this context, we strengthen an APX-hardness result in the literature, and also show a simple but strong W-hardness result.