Asadpour, Feige, and Saberi proved that the integrality gap of the configuration LP for the restricted max-min allocation problem is at most $4$. However, their proof does not give a polynomial-time approximation algorithm. A lot of efforts have been devoted to designing an efficient algorithm whose approximation ratio can match this upper bound for the integrality gap. In ICALP 2018, we present a $(6 + delta)$-approximation algorithm where $delta$ can be any positive constant, and there is still a gap of roughly $2$. In this paper, we narrow the gap significantly by proposing a $(4+delta)$-approximation algorithm where $delta$ can be any positive constant. The approximation ratio is with respect to the optimal value of the configuration LP, and the running time is $mathit{poly}(m,n)cdot n^{mathit{poly}(frac{1}{delta})}$ where $n$ is the number of players and $m$ is the number of resources. We also improve the upper bound for the integrality gap of the configuration LP to $3 + frac{21}{26} approx 3.808$.
Download