Approximation and parameterized complexity of minimax approval voting

DOI10.1613/JAIR.1.11253zbMATH Open1451.68130arXiv1607.07906OpenAlexW2903252999WikidataQ128873806 ScholiaQ128873806MaRDI QIDQ4558792FDOQ4558792

Authors: Marek Cygan, Łukasz Kowalik, Arkadiusz Socała, Krzysztof Sornat 

Publication date: 30 November 2018

Published in: Journal of Artificial Intelligence Research (Search for Journal in Brave)

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 $mathcal{O}^{s}tar(2^{o(dlogd)})$, unless the Exponential Time Hypothesis (ETH) fails. This means that the $mathcal{O}^{s}tar(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 $mathcal{O}^{s}tar(left(3/epsilonight{)}^{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^{mathcalO(1/epsilo{n}^{2}cdotlog(1/epsilon))}cdotmathrmpoly(m)$, almost matching the running time of the fastest known PTAS for Closest String due to Ma and Sun [SIAM J. Comp. 2009].

Full work available at URL: https://arxiv.org/abs/1607.07906

Recommendations

• PTAS for minimax approval voting
• Chamberlin-Courant rule with approval ballots: approximating the MaxCover problem with bounded frequencies in FPT time
• On the approximability of Dodgson and Young elections
• Socially desirable approximations for dodgson’s voting rule
• Parameterized complexity of control and bribery for \(d\)-approval elections

zbMATH Keywords

approximationcomputational social choicecompitational speed

Mathematics Subject Classification ID

Social choice (91B14) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Cited In (6)

• Multiwinner analogues of the plurality rule: axiomatic and algorithmic perspectives
• Parameterized dichotomy of choosing committees based on approval votes in the presence of outliers
• The minimum approval mechanism implements the efficient public good allocation theoretically and experimentally
• An approval-voting polytope for linear orders
• Chamberlin-Courant rule with approval ballots: approximating the MaxCover problem with bounded frequencies in FPT time
• PTAS for minimax approval voting

This page was built for publication: Approximation and parameterized complexity of minimax approval voting

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4558792)