Abstract. In this paper, we give the first approximation algorithm for the problem of max-min fair allocation of indivisible goods. An instance of this problem consists of a set of k people and m indivisible goods. Each person has a known linear utility function over the set of goods which might be different from the utility functions of other people. The goal is to distribute the goods among the people and maximize the minimum utility received by them. The approximation ratio of our algorithm is Ω( As a crucial part of our algorithm, we design and analyze an iterative method for rounding a fractional matching on a tree which might be of independent interest. We also provide better bounds when we are allowed to exclude a small fraction of the people from the problem. 1. Introduction. Fair division, also known as the cake cutting problem, has been studied extensively, mostly with a measure theoretic or combinatorial perspective in mathematics literature since the 1950s [26] . More recently this problem has been brought to the attention of the computer science community, in which the emphasis is more on designing efficient algorithms [24, 21, 22] . Moving beyond the metaphor of cake, the focus of most of these works is on practical cases where the goods are less divisible. An interested reader can consult [9] for a long list of applications of these problems. In this paper, we study the problem of max-min fair allocation of indivisible goods. In our setting, we are allocating m goods to k persons. Each person i has a nonnegative integer valuation u ij for good j. We assume that the valuation functions are linear; i.e. u i,C = j∈C u ij for any set C of goods. The goal is to allocate each good to a person such that the least happy person is as happy as possible. More formally, we want to maximize min i u i,Ci , where C i is the set of goods allocated to person i. This problem is very similar in nature to job scheduling problems especially minimum makespan scheduling [23] . However, applications of techniques such as rounding the assignment linear program [8, 16] has not yielded algorithms with an approximation ratio better than O(1/k) for this problem so far. Namely, the assignment LP used in [23] yields an additive approximation of max ij u ij [8]; i.e. it can be used to find a solution of value at least OPT − max ij u ij , where OPT is the value of the optimal solution. Unfortunately, it offers no multiplicative approximation guarantee in the most challenging cases of the problem when OPT ≤ max ij u ij . In the case of subadditive utility functions, Khot and Ponnuswami [20] provide a (2k − 1)-approximation algorithm. Bezakova and Dani [8] showed that this problem is hard to approximate within a factor better than
Subsequently, REF provided a rounding scheme for this LP to obtain a feasible solution of value no worse than O(
An Approximation Algorithm for Max-Min Fair Allocation of Indivisible Goods
SIAM J. Comput.
SIAM J. Comput.
Mathematics Computer Science