arXiv preprint ·
Integrality Gap of 3.4 for Santa Claus: A Topology-based Analysis
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Explicit Subspace Evasive Sets via Subspace Designs
Polynomial Swap Coboundary Expansion with Applications to LTCs and PCPs
Small classes have linear neighbourhood complexity
Improved Lower Bounds for Mutually Orthogonal Latin Squares (MOLS) at 33 Orders
When Elements Fail: Weighted Fault-Tolerant Matroid Bases
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.