An Algorithmic Framework for Approximating Maximin Share Allocation of Chores
An Algorithmic Framework for Approximating Maximin Share Allocation of Chores
复制标题
近似最大最小份额分配家务的算法框架
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
P. Lu
中科院分区：
文献类型：
--
作者：
Xin Huang;P. Lu
我们考虑在n个代理人之间公平地划分m个不可分割的家务的问题。我们在这里考虑的公平性度量是最小份额。以前最著名的结果是，总是存在一个4/3近似的最小份额分配[3]。使用我们的算法，我们总是可以找到一个11/9近似的最小份额分配的任何实例。我们还讨论了如何提高算法的效率及其与作业调度问题的联系。全文可在https://arxiv.org/abs/1907.04505上找到。
We consider the problem of fairly dividing m indivisible chores among n agents. The fairness measure we consider here is the maximin share. The previous best known result is that there always exists a 4/3-approximation maximin share allocation[3]. With our algorithm, we can always find a 11/9-approximation maximin share allocation for any instance. We also discuss how to improve the efficiency of the algorithm and its connection to the job scheduling problem. The full paper can be found at https://arxiv.org/abs/1907.04505.
DOI：
10.1145/3391403.3399526
发表时间：
2019-02
期刊：
Proceedings of the 21st ACM Conference on Economics and Computation
影响因子：
--
作者：
J. Garg;Setareh Taki
通讯作者：
J. Garg;Setareh Taki
EFX 存在三个代理
DOI：
10.1145/3391403.3399511
发表时间：
2020
期刊：
EC '20: Proceedings of the 21st ACM Conference on Economics and Computation
影响因子：
--
作者：
Chaudhury, Bhaskar R.;Garg, Jugal;Mehlhorn, Kurt
通讯作者：
Mehlhorn, Kurt