  We revisit the problem max-min degree arborescence, which was introduced by
Bateni et al. [STOC'09] as a central special case of the general Santa Claus
problem, which constitutes a notorious open question in approximation
algorithms. In the former problem we are given a directed graph with sources
and sinks and our goal is 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 Santa Claus problem: (1) like in the Santa Claus problem
the configuration LP has a large integrality gap in this case and (2) previous
progress by Bateni et al. was quickly generalized to the Santa Claus problem
(Chakrabarty et al. [FOCS'09]). These results remain the state-of-the-art both
for the Santa Claus problem and for max-min degree arborescence and they yield
a polylogarithmic approximation in quasi-polynomial time. We present an
exponential improvement to this, a $\mathrm{poly}(\log\log n)$-approximation in
quasi-polynomial time for the max-min degree arborescence problem. To the best
of our knowledge, this is the first example of breaking the logarithmic barrier
for a special case of the Santa Claus problem, where the configuration LP
cannot be utilized.
