Approximation and Parameterized Complexity of Minimax Approval Voting

No. 1: Thirty-First AAAI Conference On Artificial Intelligence

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 31

AAAI Technical Track: Game Theory and Economic Paradigms

We present three results on the complexity of MINIMAX APPROVAL VOTING. First, we study MINIMAX APPROVAL VOTING parameterized by the Hamming distance d from the solution to the votes. We show MINIMAX APPROVAL VOTING admits no algorithm running in time O_(2o(d log d), unless the Exponential Time Hypothesis (ETH) fails. This means that the O_(d2d) algorithm of Misra et al. (AAMAS 2015) is essentially optimal. Motivated by this, we then show a parameterized approximation scheme, running in time O_((3/_)2d), which is essentially tight assuming ETH. Finally, we get a new polynomial-time randomized approximation scheme for MINIMAX APPROVAL VOTING, which runs in time nO(1/_2álog(1/_))á poly(m), almost matching the running time of the fastest known PTAS for CLOSEST STRING due to Ma and Sun (SIAM J. Comp. 2009).

10.1609/aaai.v31i1.10575