Ko, Sheng YenSheng YenKoCHEN HO-LINCheng, Siu WingSiu WingChengHon, Wing KaiWing KaiHonLiao, Chung ShouChung ShouLiao2023-03-132023-03-132023-01-0101784617https://scholars.lib.ntu.edu.tw/handle/123456789/629242In 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.Approximation algorithms | Hypergraph matching | Max–min allocationjournal article10.1007/s00453-023-01105-32-s2.0-85148955372https://api.elsevier.com/content/abstract/scopus_id/85148955372