Abstract
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.