{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,20]],"date-time":"2026-04-20T02:16:34Z","timestamp":1776651394854,"version":"3.51.2"},"reference-count":0,"publisher":"IOS Press","isbn-type":[{"value":"9781643684369","type":"print"},{"value":"9781643684376","type":"electronic"}],"license":[{"start":{"date-parts":[[2023,9,28]],"date-time":"2023-09-28T00:00:00Z","timestamp":1695859200000},"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":[[2023,9,28]]},"abstract":"<jats:p>Using insights from parametric integer linear programming, we improve the work of Bredereck et al.\u00a0[Proc.\u00a0ACM\u00a0EC\u00a02019] on high-multiplicity fair allocation. Answering an open question from their work, we proved that the problem of finding envy-free Pareto-efficient allocations of indivisible items is fixed-parameter tractable with respect to the combined parameter \u201cnumber of agents\u201d plus \u201cnumber of item types.\u201d Our central improvement, compared to their result, is to break the condition that the corresponding utility and multiplicity values have to be encoded in unary, which is required there. Concretely, we show that, while preserving fixed-parameter tractability, these values can be encoded in binary. Thus, we substantially expand the range of feasible utility and multiplicity values.<\/jats:p>","DOI":"10.3233\/faia230284","type":"book-chapter","created":{"date-parts":[[2023,9,29]],"date-time":"2023-09-29T09:01:16Z","timestamp":1695978076000},"source":"Crossref","is-referenced-by-count":1,"title":["High-Multiplicity Fair Allocation Using Parametric Integer Linear Programming"],"prefix":"10.3233","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6303-6276","authenticated-orcid":false,"given":"Robert","family":"Bredereck","sequence":"first","affiliation":[{"name":"Institut f\u00fcr Informatik, TU Clausthal, Clausthal-Zellerfeld, Germany"},{"name":"Technische Universit\u00e4t Berlin, Berlin, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1401-0157","authenticated-orcid":false,"given":"Andrzej","family":"Kaczmarczyk","sequence":"additional","affiliation":[{"name":"AGH University, Krak\u00f3w, Poland"},{"name":"Technische Universit\u00e4t Berlin, Berlin, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2588-5709","authenticated-orcid":false,"given":"Du\u0161an","family":"Knop","sequence":"additional","affiliation":[{"name":"Czech Technical University in Prague, Prague, Czech Republic"},{"name":"Technische Universit\u00e4t Berlin, Berlin, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1703-1236","authenticated-orcid":false,"given":"Rolf","family":"Niedermeier","sequence":"additional","affiliation":[{"name":"Technische Universit\u00e4t Berlin, Berlin, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"7437","container-title":["Frontiers in Artificial Intelligence and Applications","ECAI 2023"],"original-title":[],"link":[{"URL":"https:\/\/ebooks.iospress.nl\/pdf\/doi\/10.3233\/FAIA230284","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,29]],"date-time":"2023-09-29T09:01:18Z","timestamp":1695978078000},"score":1,"resource":{"primary":{"URL":"https:\/\/ebooks.iospress.nl\/doi\/10.3233\/FAIA230284"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,9,28]]},"ISBN":["9781643684369","9781643684376"],"references-count":0,"URL":"https:\/\/doi.org\/10.3233\/faia230284","relation":{},"ISSN":["0922-6389","1879-8314"],"issn-type":[{"value":"0922-6389","type":"print"},{"value":"1879-8314","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,9,28]]}}}