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

Abstract:

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 p_ij 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 min_i Sum(of among items given to kid i) p_ij. The authors give an O(log log m / log log log m) approximation for the restricted assignment case of the problem where p_ij is in {p_j, 0} (That is, each present j has either value p_j or 0 for each kid}.

(from STOC 2006)