{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,29]],"date-time":"2026-09-29T02:08:35Z","timestamp":1790647715086,"version":"4.1.0"},"publisher-location":"California","reference-count":0,"publisher":"International Joint Conferences on Artificial Intelligence Organization","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020,7]]},"abstract":"<jats:p>In approval-based multiwinner elections, we are given a set of voters, a set of candidates, and, for each voter, a set of candidates approved by the voter. The goal is to find a committee of size k that maximizes the total utility of the voters. In this paper, we study approximability of Thiele rules, which are known to be NP-hard to solve exactly. We provide a tight polynomial time approximation algorithm for a natural class of geometrically dominant weights that includes such voting rules as Proportional Approval Voting or p-Geometric. The algorithm is relatively simple: first we solve a linear program and then we round a solution by employing a framework called pipage rounding due to Ageev and Sviridenko (2004) and Calinescu et al. (2011). We provide a matching lower bound via a reduction from the Label Cover problem. Moreover, assuming a conjecture called Gap-ETH, we show that better approximation ratio cannot be obtained even in time f(k)*pow(n,o(k)).<\/jats:p>","DOI":"10.24963\/ijcai.2020\/39","type":"proceedings-article","created":{"date-parts":[[2020,7,8]],"date-time":"2020-07-08T12:12:10Z","timestamp":1594210330000},"page":"276-282","source":"Crossref","is-referenced-by-count":9,"title":["Tight Approximation for Proportional Approval Voting"],"prefix":"10.24963","author":[{"given":"Szymon","family":"Dudycz","sequence":"first","affiliation":[{"name":"University of Wroc\u0142aw, Poland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Pasin","family":"Manurangsi","sequence":"additional","affiliation":[{"name":"Google Research, US"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jan","family":"Marcinkowski","sequence":"additional","affiliation":[{"name":"University of Wroc\u0142aw, Poland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Krzysztof","family":"Sornat","sequence":"additional","affiliation":[{"name":"University of Wroc\u0142aw, Poland"},{"name":"Ben-Gurion University, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"10584","event":{"name":"Twenty-Ninth International Joint Conference on Artificial Intelligence and Seventeenth Pacific Rim International Conference on Artificial Intelligence {IJCAI-PRICAI-20}","theme":"Artificial Intelligence","location":"Yokohama, Japan","acronym":"IJCAI-PRICAI-2020","number":"28","sponsor":["International Joint Conferences on Artificial Intelligence Organization (IJCAI)"],"start":{"date-parts":[[2020,7,11]]},"end":{"date-parts":[[2020,7,17]]}},"container-title":["Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence"],"original-title":[],"deposited":{"date-parts":[[2020,7,9]],"date-time":"2020-07-09T02:13:00Z","timestamp":1594260780000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ijcai.org\/proceedings\/2020\/39"}},"subtitle":[],"proceedings-subject":"Artificial Intelligence Research Articles","short-title":[],"issued":{"date-parts":[[2020,7]]},"references-count":0,"URL":"https:\/\/doi.org\/10.24963\/ijcai.2020\/39","relation":{},"subject":[],"published":{"date-parts":[[2020,7]]}}}