Approximation and Parameterized Complexity of Minimax Approval Voting

[摘要] 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*(2^{o(d log d)}), unless the Exponential Time Hypothesis (ETH) fails. This means that the O*(d^2d) algorithm of Misra, Nabeel and Singh 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 n^{O(1/ε2⋅log(1/ε))}⋅poly(m), where n is a number of voters and m is a number of alternatives. It almost matches the running time of the fastest known PTAS for Closest String due to Ma and Sun.

[学科分类] 人工智能