arXiv preprint ·

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

Kimon Boehmer and Chien-Chung Huang

Published
Source
arXiv preprint, posted before peer review
Original
Read it at arXiv
Topics
Data Structures & AlgorithmsDiscrete Mathematics

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.

Already a reader? Sign in

All new papers in Data Structures & Algorithms

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.

Papers belong to their authors and publishers; every page here links to the original. All research topics