Combinatorial Algorithm for Restricted Max-Min Fair Allocation
Chidambaram Annamalai, Christos Kalaitzis, Ola Svensson · ACM Transactions on Algorithms · 2017
We study the basic allocation problem of assigning resources to players to maximize fairness. This is one of the few natural problems that enjoys the intriguing status of having a better estimation algorithm than approximation algorithm. Indeed, a certain Configuration-LP can be used to estimate the value of the optimal allocation to within a factor of 4+ ε. In contrast, however, the best-known approximation algorithm for the problem has an unspecified large constant guarantee. In this article, we significantly narrow this gap by giving a 13-approximation algorithm for the problem. Our approach develops a local search technique introduced by Haxell [13] for hypergraph matchings and later used in this context by Asadpour, Feige, and Saberi [2]. For our local search procedure to terminate in polynomial time, we introduce several new ideas, such as lazy updates and greedy players . Besides the improved approximation guarantee, the highlight of our approach is that it is purely combinatorial and uses the Configuration-LP only in the analysis.