Name
Abstract | ||
|---|---|---|
AbstractWe present three results on the complexity of MINNIMAX APPROVAL VOTING. First, we study MINNIMAX APPROVAL VOTING parameterized by the Hamming distance d from the solution to the votes. We show MINNIMAX 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, 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 MINNIMAX APPROVAL VOTING, which runs in time nO(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. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1613/jair.1.11253 | Hosted Content |
DocType | Volume | Issue |
Conference | 63 | 1 |
ISSN | Citations | PageRank |
1076-9757 | 1 | 0.35 |
References | Authors | |
10 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Marek Cygan | 1 | 556 | 40.52 |
| Łukasz Kowalik | 2 | 11 | 1.26 |
| Arkadiusz Socala | 3 | 11 | 4.37 |
| Krzysztof Sornat | 4 | 6 | 3.20 |