MaxMin allocation via degree lower-bounded arborescences

We consider the problem of MaxMin allocation of indivisible goods. There are m items to be distributed among n players. Each player $i$ has a nonnegative valuation p ij for an item j, and the goal is to allocate items to players so as to maximize the minimum total valuation received by each player. There is a large gap in our understanding of this problem. The best known positive result is an ~O(√ n)-approximation algorithm, while there is only a factor 2 hardness known. Better algorithms are known for the restricted assignment case where each item has exactly one nonzero value for the players. We study the effect of bounded degree for items: each item has a nonzero value for at most D players. We show that essentially the case D = 3 is equivalent to the general case, and give a 4-approximation algorithm for D = 2.

Authors

• MohammadHossein Bateni
• Moses Charikar
• Venkatesan Guruswami

Keywords

• lift-and-project
• linear programming
• approximation algorithms
• graphs