Journal
ACM TRANSACTIONS ON ALGORITHMS
Volume 8, Issue 3, Pages -Publisher
ASSOC COMPUTING MACHINERY
DOI: 10.1145/2229163.2229168
Keywords
Theory; Economics; Bipartite hypergraphs; hypergraph matchings; Santa Claus problem
Funding
- NSF [0546889, 0729586]
- Israel Science Foundation [873/08]
- Direct For Computer & Info Scie & Enginr
- Division of Computing and Communication Foundations [0729586, 1216698, 0546889] Funding Source: National Science Foundation
Ask authors/readers for more resources
We consider the restricted assignment version of the problem of max-min fair allocation of indivisible goods, also known as the Santa Claus problem. There are m items and n players. Every item has some nonnegative value, and every player is interested in only some of the items. The goal is to distribute the items to the players in a way that maximizes the minimum of the sum of the values of the items given to any player. It was previously shown via a nonconstructive proof that uses the Lovasz local lemma that the integrality gap of a certain configuration LP for the problem is no worse than some (unspecified) constant. This gives a polynomial-time algorithm to estimate the optimum value of the problem within a constant factor, but does not provide a polynomial-time algorithm for finding a corresponding allocation. We use a different approach to analyze the integrality gap. Our approach is based upon local search techniques for finding perfect matchings in certain classes of hypergraphs. As a result, we prove that the integrality gap of the configuration LP is no worse than 1/4. Our proof provides a local search algorithm which finds the corresponding allocation, but is nonconstructive in the sense that this algorithm is not known to converge to a local optimum in a polynomial number of steps.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available