Title: Better Trees for Santa Claus

Abstract: A notorious open problem in approximation algorithms is whether there exists a constant factor approximation for MaxMin Fair Allocation of indivisible items (also known as the Santa Claus problem). Bateni, Charikar, and Guruswami [STOC'09] introduced the MaxMin Arborescence problem as an important special case: Given a directed graph with sources and sinks we have to find vertex disjoint arborescences rooted in the sources such that at each non-sink vertex of an arborescence the out-degree is at least k, where k is to be maximized.

This problem is of particular interest, since it appears to capture much of the difficulty of the general Santa Claus problem. Indeed, the progress made by Bateni et al. was quickly generalized by Chakrabarty, Chuzhoy, and Khanna [FOCS’09] to the general case. These two results remain the state-of-the-art for both problems, and they yield a polylogarithmic approximation in quasi-polynomial time. In this talk, I will present the main ideas behind an exponential improvement to this, a poly(loglog n)-approximation in quasi-polynomial time for the MaxMin Arborescence problem.

This talk is based on a joint work with Lars Rohwedder. https://arxiv.org/abs/2211.14259