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 paper we give a PTAS for the Minimax Approval Voting problem. Our work is based on the PTAS for Closest String @cite_1 , which is a similar problem to @math but there we do not have the restriction on the number of 1's in the result. Technically, our contribution is the method of handling the number of 1's in the output. We also believe that our presentation is somewhat more intuitive.
@cite_1
2047386086
The problem of finding a center string that is "close" to everygiven string arises in computational molecular biology and codingtheory. This problem has two versions: the Closest String problemand the Closest Substring problem. Given a set of strings S= s1, s2, ...,sn , each of length m, the Closest Stringproblem is to find the smallest d and a string s of lengthm which is within Hamming distance d to eachsi e S. This problem comes fromcoding theory when we are looking for a code not too far away froma given set of codes. Closest Substring problem, with an additionalinput integer L, asks for the smallest d and a strings, of length L, which is within Hamming distance daway from a substring, of length L, of each si. This problemis much more elusive than the Closest String problem. The ClosestSubstring problem is formulated from applications in findingconserved regions, identifying genetic drug targets and generatinggenetic probes in molecular biology. Whether there are efficientapproximation algorithms for both problems are major open questionsin this area. We present two polynomial-time approximationalgorithms with approximation ratio 1 + e for any smalle to settle both questions.