Recent developments on the Santa Claus problem
We consider the max-min fair allocation problem. There are
players and resources and each player assigns each resource
a certain value. The goal is to assign the resources in such
a way that one maximizes the minimum total value given to
a player. We will discuss the developments of this problem
and we will zoom in at a special case, the restricted
max-min fair allocation problem or Santa Claus problem.
Recently different approaches were used for this problem to
get a constant factor approximation algorithm.
We will discuss a powerful linear program and how this is
used to get a local search algorithm on hypergraphs. Since
this algorithm is not known to converge in polynomial time
we made a complex instance for which the algorithm will
have a quasi-polynomial running time. We will discuss the
high level ideas of this instance, directly giving insight
how the algorithm works.