期刊
ACM TRANSACTIONS ON ALGORITHMS
卷 8, 期 3, 页码 -出版社
ASSOC COMPUTING MACHINERY
DOI: 10.1145/2229163.2229168
关键词
Theory; Economics; Bipartite hypergraphs; hypergraph matchings; Santa Claus problem
资金
- 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
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据