## 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)