Lift-and-Project Integrality Gaps for Santa Claus

This paper is devoted to the study of the MaxMinDegree Arborescence (MMDA) problem in layered directed graphs of depth ℓ ≤ O(log n/ log log n), which is an important special case of the Santa Claus problem. Obtaining a polylogarithmic approximation for MMDA in polynomial time is of high interest as it is a necessary condition to improve upon the well-known 2-approximation for makespan scheduling on unrelated machines by Lenstra, Shmoys, and Tardos [FOCS'87].

The only way we have to solve the MMDA problem within a polylogarithmic factor is via an elegant recursive rounding of the (ℓ -1) th level of the Sherali-Adams hierarchy, which needs time n O(ℓ) to solve. However, it remains plausible that one could obtain a polylogarithmic approximation in polynomial time by using the same rounding with only 1 round of the Sherali-Adams hierarchy.

As a main result, we rule out this possibility by constructing an MMDA instance of depth 3 for which an integrality gap of n Ω(1) survives 1 round of the Sherali-Adams hierarchy. This result is tight since it is known that after only 2 rounds the gap is at most polylogarithmic on depth-3 graphs. Second, we show that our instance can be "lifted" via a simple trick to MMDA instances of any depth ℓ ∈ Ω(1) ∩ o(log n/ log log n) (the whole range of interest), for which we conjecture that an integrality gap of n Ω(1/ℓ) survives Ω(ℓ) rounds of Sherali-Adams. We show a number of intermediate results towards this conjecture, which also suggest that our construction is a significant challenge to the techniques used so far for Santa Claus.

The main inspiration of this work stems from a beautiful construction by Li and Laekhanukit [SODA'22] used in the context of the Directed Steiner Tree problem. Inspired by their construction, we build an MMDA instance of depth 3 which has interesting properties, and we show how to use the labeling scheme underlying the construction in a novel way to quantify non-trivial correlations between different edges of the graph. Our techniques also seem relevant in the world of Directed Steiner Trees, so we are hopeful they will transfer.