An Improved Approximation Algorithm for Maximin Shares
An Improved Approximation Algorithm for Maximin Shares
复制标题
DOI：
10.1145/3391403.3399526
复制
发表时间：
2019-02
期刊：
影响因子：
--
通讯作者：
J. Garg;Setareh Taki
中科院分区：
文献类型：
--
作者：
J. Garg;Setareh Taki
我们研究的问题，公平分配的m个不可分割的项目之间的n个代理商与添加剂的估值使用流行的概念，最大的份额（MMS）作为我们的公平性的措施。MMS分配为每个代理提供了一个捆绑包，价值至少为她的最小份额。虽然我们知道这样的分配不需要存在[5，7]，但一系列出色的工作[1-3，6，7]提供了2/3近似算法，在该算法中，每个代理人收到的捆绑价值至少是她最大最小份额的2/3倍。最近，[4]表明存在3/4 MMS分配和PTAS以找到3/4 - ε MMS分配。大多数以前的作品利用复杂的算法，并需要代理的近似MMS值，这是计算昂贵的获得。
We study the problem of fair allocation of m indivisible items among n agents with additive valuations using the popular notion of maximin share (MMS) as our measure of fairness. An MMS allocation provides each agent a bundle worth at least her maximin share. While it is known that such an allocation need not exist [5, 7], a series of remarkable work [1-3, 6, 7] provided 2/3 approximation algorithms in which each agent receives a bundle worth at least 2/3 times her maximin share. More recently, [4] showed the existence of 3/4 MMS allocations and a PTAS to find a 3/4 - ε MMS allocation. Most of the previous works utilize intricate algorithms and require agents' approximate MMS values, which are computationally expensive to obtain.