Approximation and Parameterized Complexity of Minimax Approval Voting

Authors

  • Marek Cygan University of Warsaw
  • Łukasz Kowalik University of Warsaw
  • Arkadiusz Socała University of Warsaw
  • Krzysztof Sornat University of Wroclaw

DOI:

https://doi.org/10.1609/aaai.v31i1.10575

Keywords:

minimax approval voting, computational social choice, lower bound, parameterized complexity, ptas

Abstract

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).

AAAI-2017 Proceedings Cover

Downloads

Published

2017-02-10

How to Cite

Cygan, M., Kowalik, Łukasz, Socała, A., & Sornat, K. (2017). Approximation and Parameterized Complexity of Minimax Approval Voting. Proceedings of the AAAI Conference on Artificial Intelligence, 31(1). https://doi.org/10.1609/aaai.v31i1.10575

Issue

Vol. 31 No. 1 (2017): Thirty-First AAAI Conference on Artificial Intelligence

Section

AAAI Technical Track: Game Theory and Economic Paradigms