Artykuł w czasopiśmie
Brak miniatury
Licencja
ClosedAccessDostęp zamknięty
 

Approximation and Parameterized Complexity of Minimax Approval Voting

Uproszczony widok
dc.abstract.enWe 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*(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 Minimax 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.
dc.affiliationUniwersytet Warszawski
dc.contributor.authorSocała, Arkadiusz
dc.contributor.authorSornat, Krzysztof
dc.contributor.authorCygan, Marek
dc.contributor.authorKowalik, Łukasz
dc.date.accessioned2024-01-24T16:55:18Z
dc.date.available2024-01-24T16:55:18Z
dc.date.issued2018
dc.description.financeNie dotyczy
dc.description.volume63
dc.identifier.doi10.1613/JAIR.1.11253
dc.identifier.issn1076-9757
dc.identifier.urihttps://repozytorium.uw.edu.pl//handle/item/101056
dc.languageeng
dc.pbn.affiliationcomputer and information sciences
dc.relation.ispartofJournal of Artificial Intelligence Research
dc.relation.pages495 - 513
dc.rightsClosedAccess
dc.sciencecloudnosend
dc.titleApproximation and Parameterized Complexity of Minimax Approval Voting
dc.typeJournalArticle
dspace.entity.typePublication