Santa claus meets hypergraph matchings
Santa claus meets hypergraph matchings
复制标题
圣诞老人遇见超图匹配
DOI：
--
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
A. Saberi
中科院分区：
文献类型：
--
作者：
A. Asadpour;U. Feige;A. Saberi
我们考虑不可分割物品的最大最小公平分配问题的限制分配版本，也称为圣诞老人问题。这里有m个道具和n个玩家。每个道具都有一些非负值，每个玩家只对其中一些道具感兴趣。我们的目标是将道具分配给玩家，使所有玩家获得的道具价值总和的最小值最大化。先前通过使用Lovász局部引理的非建设性证明证明了该问题的某个构型LP的完整性间隙不小于某个（未指定的）常数。这给出了一个多项式时间算法来估计一个常数因子内问题的最优值，但没有提供一个多项式时间算法来寻找相应的分配。
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 Lovász 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.