https://scholars.lib.ntu.edu.tw/handle/123456789/606973
標題: | General Max-Min Fair Allocation | 作者: | Ko S.-Y Chen H.-L Cheng S.-W Hon W.-K Liao C.-S. CHEN HO-LIN |
關鍵字: | Approximation algorithms;Hypergraph matching;Max-min allocation;Polynomial approximation;Rate constants;Estimation strategies;Fair allocation;Hyper graph;Matchings;Max/min;Maximum ratio;Over-estimation;Resource utility | 公開日期: | 2021 | 卷: | 13025 LNCS | 起(迄)頁: | 63-75 | 來源出版物: | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) | 摘要: | In the general max-min fair allocation, also known as the Santa Claus problem, there are m players and n indivisible resources, each player has his/her own utilities for the resources, and the goal is to find an assignment that maximizes the minimum total utility of resources assigned to a player. We introduce an over-estimation strategy to help overcome the challenges of each resource having different utilities for different players. When all resource utilities are positive, we transform it to the machine covering problem and find a (c1-?) -approximate allocation in polynomial running time for any fixed ?? (0, 1 ), where c is the maximum ratio of the largest utility to the smallest utility of any resource. When some resource utilities are zero, we apply the approximation algorithm of Cheng and Mao?[9] for the restricted max-min fair allocation problem. It gives a (1 + 3 c^ + O(δc^ 2) ) -approximate allocation in polynomial time for any fixed δ? (0, 1 ), where c^ is the maximum ratio of the largest utility to the smallest positive utility of any resource. The approximation ratios are reasonable if c and c^ are small constants; for example, when the players rate the resources on a 5-point scale. ? 2021, Springer Nature Switzerland AG. |
URI: | https://www.scopus.com/inward/record.uri?eid=2-s2.0-85118180335&doi=10.1007%2f978-3-030-89543-3_6&partnerID=40&md5=cd83098b599dd2ffbe15578a04477d04 https://scholars.lib.ntu.edu.tw/handle/123456789/606973 |
ISSN: | 03029743 | DOI: | 10.1007/978-3-030-89543-3_6 |
顯示於: | 電機工程學系 |
在 IR 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。