Integrality Gap of the Configuration LP for the Restricted Max-Min Fair Allocation
share
The max-min fair allocation problem seeks an allocation of resources to players that maximizes the minimum total value obtained by any player. Each player p has a non-negative value v_pr on resource r. In the restricted case, we have v_pr∈{v_r, 0}. That is, a resource r is worth value v_r for the players who desire it and value 0 for the other players. In this paper, we consider the configuration LP, a linear programming relaxation for the restricted problem. The integrality gap of the configuration LP is at least 2. Asadpour, Feige, and Saberi proved an upper bound of 4. We improve the upper bound to 23/6 using the dual of the configuration LP. Since the configuration LP can be solved to any desired accuracy δ in polynomial time, our result leads to a polynomial-time algorithm which estimates the optimal value within a factor of 23/6+δ.
READ FULL TEXT