General Max-Min Fair Allocation
Journal
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Journal Volume
13025 LNCS
Pages
63-75
Date Issued
2021
Author(s)
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. ? 2021, Springer Nature Switzerland AG.
Subjects
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
Type
conference paper