A note on the integrality gap of the configuration LP for restricted Santa Claus

摘要

In the restricted Santa Claus problem we are given resources R and players P. Every resource j is an element of R. has a value v(j) and every player i is an element of P desires a set of resources R(i). We are interested in distributing the resources to players that desire them. The quality of a solution is measured by the least happy player, i.e., the lowest sum of resource values. This value should be maximized. The local search algorithm by Asadpour et al. [1] and its connection to the configuration LP has proved itself to be a very influential technique for this and related problems.Asadpour et al. used a local search to obtain a bound of 4 for the ratio of the fractional to the integral optimum of the configuration LP (the integrality gap). This bound is non-constructive, since the local search has not been shown to terminate in polynomial time. On the negative side, the worst instance known has an integrality gap of 2.Although much progress was made in this area, neither bound has been improved since. We present a better analysis that shows the integrality gap is not worse than 3 + 5/6 approximate to 3.8333. (C) 2020 Elsevier B.V. All rights reserved.