Понедельник, 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 $](../../../sites/default/files/tex/3579696f06fe2e58f62d997256e0c9d669e94672/index.png)
strings of length
![$ m $](../../../sites/default/files/tex/05b806fb3a39e75606f12e544fec1ae578c32b0b/index.png)
(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 $](../../../sites/default/files/tex/f5efd7e164b692a1c06faa4659d1c840d8761de8/index.png)
from the solution to the votes. We show Minimax Approval Voting admits no algorithm running in time
![$ O^*(2^{o(d\log d)}) $](../../../sites/default/files/tex/030cff1e4bd7c8031b93bcea4553dd5b04893ab2/index.png)
, unless the Exponential Time Hypothesis (ETH) fails. This means that the
![$ O^*(d^{2d}) $](../../../sites/default/files/tex/460256232f10d4e18a7a2d96d1a24886ee755bbe/index.png)
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}) $](../../../sites/default/files/tex/390a3b919015d40c7099e8debeafa0c16f637f11/index.png)
, 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) $](../../../sites/default/files/tex/def26e76d55c16542a2900a14ec52d944e377953/index.png)
, 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