{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,22]],"date-time":"2025-10-22T23:36:14Z","timestamp":1761176174700,"version":"build-2065373602"},"reference-count":0,"publisher":"IOS Press","isbn-type":[{"value":"9781643686318","type":"electronic"}],"license":[{"start":{"date-parts":[[2025,10,21]],"date-time":"2025-10-21T00:00:00Z","timestamp":1761004800000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2025,10,21]]},"abstract":"<jats:p>Approval-Based Committee (ABC) rules are an important tool for choosing a fair set of candidates when given the preferences of a collection of voters. Though finding a winning committee for many ABC rules is NP-hard, natural variations for these rules with polynomial-time algorithms exist. The recently introduced Method of Equal Shares, an important ABC rule with desirable properties, is also computable in polynomial time. However, when working with very large elections, polynomial time is not enough and parallelization may be necessary. We show that computing a winning committee using these polynomial-time ABC rules (including the Method of Equal Shares) is P-hard, thus showing they cannot be parallelized. In contrast, we show that finding a winning committee can be parallelized when the votes are single-peaked or single-crossing for the important ABC rule Chamberlin-Courant.<\/jats:p>","DOI":"10.3233\/faia251005","type":"book-chapter","created":{"date-parts":[[2025,10,22]],"date-time":"2025-10-22T09:48:31Z","timestamp":1761126511000},"source":"Crossref","is-referenced-by-count":0,"title":["On the Parallelizability of Approval-Based Committee Rules"],"prefix":"10.3233","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5147-9646","authenticated-orcid":false,"given":"Zack","family":"Fitzsimmons","sequence":"first","affiliation":[{"name":"Department of Math.\u00a0and Computer Science, College of the Holy Cross, Worcester, MA 01610"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5590-5235","authenticated-orcid":false,"given":"Zohair Raza","family":"Hassan","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Rochester Institute of Technology, Rochester, NY 14623"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7115-626X","authenticated-orcid":false,"given":"Edith","family":"Hemaspaandra","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Rochester Institute of Technology, Rochester, NY 14623"}]}],"member":"7437","container-title":["Frontiers in Artificial Intelligence and Applications","ECAI 2025"],"original-title":[],"link":[{"URL":"https:\/\/ebooks.iospress.nl\/pdf\/doi\/10.3233\/FAIA251005","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,22]],"date-time":"2025-10-22T09:48:31Z","timestamp":1761126511000},"score":1,"resource":{"primary":{"URL":"https:\/\/ebooks.iospress.nl\/doi\/10.3233\/FAIA251005"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,10,21]]},"ISBN":["9781643686318"],"references-count":0,"URL":"https:\/\/doi.org\/10.3233\/faia251005","relation":{},"ISSN":["0922-6389","1879-8314"],"issn-type":[{"value":"0922-6389","type":"print"},{"value":"1879-8314","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,10,21]]}}}