https://scholars.lib.ntu.edu.tw/handle/123456789/629242
標題: | Polynomial-time Combinatorial Algorithm for General Max–Min Fair Allocation | 作者: | Ko, Sheng Yen CHEN HO-LIN Cheng, Siu Wing Hon, Wing Kai Liao, Chung Shou |
關鍵字: | Approximation algorithms | Hypergraph matching | Max–min allocation | 公開日期: | 1-一月-2023 | 來源出版物: | Algorithmica | 摘要: | In the general max–min fair allocation 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. The problem finds many natural applications such as bandwidth distribution in telecom networks, processor allocation in computational grids, and even public-sector decision making. We introduce an over-estimation strategy to design approximation algorithms for this problem. When all utilities are positive, we obtain an approximation ratio of c1-ϵ, where c is the maximum ratio of the largest utility to the smallest utility of any resource. When some utilities are zero, we obtain an approximation ratio of (1 + 3 c^ + O(δc^ 2)) , where c^ is the maximum ratio of the largest utility to the smallest positive utility of any resource. |
URI: | https://scholars.lib.ntu.edu.tw/handle/123456789/629242 | ISSN: | 01784617 | DOI: | 10.1007/s00453-023-01105-3 |
顯示於: | 電機工程學系 |
在 IR 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。