As a guest user you are not logged in or recognized by your IP address. You have
access to the Front Matter, Abstracts, Author Index, Subject Index and the full
text of Open Access publications.
Using insights from parametric integer linear programming, we improve the work of Bredereck et al. [Proc. ACM EC 2019] 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 “number of agents” plus “number of item types.” 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.