Home

Понедельник 17.10. Krzysztof Sornat: "Approximation and Parameterized Complexity of Minimax Approval Voting"

Понедельник, 17 октября, ауд. 106. Начало в 14:00.

Докладчик: Krzysztof Sornat (University of Wroclaw).

Тема: Approximation and Parameterized Complexity of Minimax Approval Voting.

Abstract

We present three results on the complexity of Minimax Approval Voting that is a voting rule for choosing committee of fixed size k. Here, we see the votes and the choice as $ 0-1 $ strings of length $ m $ (characteristic vectors of the subsets). The goal is to minimize the maximum Hamming distance to a vote. 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 et al. [AAMAS 2015] is essentially optimal. Motivated by this, we then show a parameterized approximation scheme, running in time $ O^*((3/\epsilon)^{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(\log(1/\epsilon)/\epsilon^2)} \cdot poly(m) $, almost matching the running time of the fastest known PTAS for Closest String due to Ma and Sun [SIAM J. Comp. 2009].

Authors: Marek Cygan, Łukasz Kowalik, Arkadiusz Socała, Krzysztof Sornat
http://arxiv.org/abs/1607.07906