arXiv:2611.15392 · v1

Integrality Gap of 3.4 for Santa Claus: A Topology-based Analysis

首次提交 2026-11-11 20:15

版本更新 2026-11-11 20:15

雷达观测 2026-11-13 11:11

摘要

In the \textsc{Max-Min Allocation} problem, a set of indivisible items are to be assigned to a set of players and the goal is to maximize the minimum value among all players. A much studied special case, the \textsc{Santa Claus} problem, assumes that an item has a fixed utility but a player is only interested in a subset of items. The main technique for designing approximation algorithms for \textsc{Santa Claus} is the configuration LP, introduced by the Bansal and Sviridenko. A long line of research has progressively improved the upper bound of the integrality gap, mostly relying on the combinatorial arguments of Haxell for finding perfect matchings in certain hypergraphs. Remarkably, a recent paper of Haxell and Szabó (SODA '23) introduced a novel topology-based analysis, by which they are able to obtain the current best upper bound of $3.534$. In this work, we adapt the approach of Haxell and Szabó to analyze the integrality gap. The main new ingredient in our adaptation is that we stop the process of "edge explosions" in a graph used by Haxell and Szabó when it becomes too costly. This early termination of explosions, combined with a new lower bound on a topological connectivity parameter based on a theorem of Aharoni, Berger, and Meshulam, allows us to improve the integrality gap to $3.4$. Our analysis has the additional advantage of being simpler.