ICS Theory Group

ICS 269, Spring 2006: Theory Seminar

Jun 9, 2006, in CS 243

The Santa Claus Problem

Authored by: Nikhil Bansal and Maxim Sviridenko

Presented by Matt Nguyen


The Santa Claus Problem is defined as follows: Santa Claus has n presents that he wants to distribute among m kids. Each kid has an arbitrary value for each present. Let pij be the value kid i has for present j. Santa's goal is to distribute presents in such a way that the least lucky kid is as happy as possible. That is, max mini Sum(of among items given to kid i) pij. The authors give an O(log log m / log log log m) approximation for the restricted assignment case of the problem where pij is in {pj, 0} (That is, each present j has either value pj or 0 for each kid}.

(from STOC 2006)