The max-min fair allocation problem, also known as the Santa Claus problem, is a fundamental problem in combinatorial optimization. Given a set of players P, a set of indivisible resources R, and a set of non-negative values {v_pr}_p∈P,r∈R, an allocation is a partition of R into disjoint subsets {C_p}_p∈P so that each player p is assigned the resources in C_p. We hope to find a fair allocation of resources to players so that the welfare of the least lucky player is maximized. More precisely, we want to maximize min_pΣ_r∈Cp v_pr. In the restricted case of this problem, we have v_pr ∈ {v_r, 0}. That is, each resource r has an intrinsic value v_r, and it is worth value v_r to those players who desire it and value 0 to those who do not.

This thesis investigates the restricted case of the probl...[ Read more ]

The max-min fair allocation problem, also known as the Santa Claus problem, is a fundamental problem in combinatorial optimization. Given a set of players P, a set of indivisible resources R, and a set of non-negative values {v_pr}_p∈P,r∈R, an allocation is a partition of R into disjoint subsets {C_p}_p∈P so that each player p is assigned the resources in C_p. We hope to find a fair allocation of resources to players so that the welfare of the least lucky player is maximized. More precisely, we want to maximize min_pΣ_r∈Cp v_pr. In the restricted case of this problem, we have v_pr ∈ {v_r, 0}. That is, each resource r has an intrinsic value v_r, and it is worth value v_r to those players who desire it and value 0 to those who do not.

This thesis investigates the restricted case of the problem, namely, the restricted max-min fair allocation. With regard to this problem, the configuration LP is the only LP relaxation known to have a constant integrality gap, and it plays an important role in estimating and approximating the optimal solution. Our first result is an improvement of the upper bound for the integrality gap from 4 to 3+21/26. It is obtained by giving a tighter analysis of a local search algorithm in the literature. Hence, by solving the configuration LP, we can estimate the optimal solution value of within a factor of 3+21/26. However, as the local search is not known to run in polynomial time, it does not lead to a polynomial-time approximation algorithm. Prior to our work, the best approximation ratio that can be achieved in polynomial time is 6 + 2√3 + δ, where δ is an arbitrarily small constant. We proposed two polynomial-time approximation algorithms. Our first algorithm achieves an approximation ratio of 6 + δ. The algorithm and its analysis are purely combinatorial. Our second algorithm achieves an approximation ratio of 4 + δ. This algorithm is also purely combinatorial while its analysis make use of the configuration LP. It generalizes the local search used in the integrality gap result.