Settling the Computational Complexity of Max-Min Allocation with Ternary Valuations

Thi Ngoc Anh Vu, Trung Thanh Nguyen, Khaled Elbassioni +1

We study the problem of computing an allocation of indivisible items that maximizes egalitarian welfare, i.e., the utility of the worst-off agent, when agents' item values or margi…