Seminar

We typically have seminars on Wednesday at noon in Malone 228.  All seminar announcements will be sent to the theory mailing list.

Jan
16
Wed
[Theory Seminar] Sami Davies
Jan 16 @ 12:00 pm – 1:00 pm

Speaker: Sami Davies
Affiliation: University of Washington

Title: A Tale of Santa Claus, Hypergraphs, and Matroids
Abstract:
A well-known problem in scheduling and approximation algorithms is the Santa Claus problem. Suppose that Santa Claus has a set of gifts, and he wants to distribute them among a set of children so that the least happy child is made as happy as possible. Here, the value that a child i has for a present j is of the form p_{ij} \in \{0,p_j\}. A polynomial time algorithm by Annamalai et al. gives a 12.33-approximation algorithm and is based on a modification of Haxell’s hypergraph matching argument.

In this paper, we introduce a matroid version of the Santa Claus problem. Our algorithm is also based on Haxell’s augmentation tree, but with the introduction of the matroid structure we solve a more general problem with cleaner methods. Our result can then be used as a blackbox to obtain a (4 +\varepsilon)-approximation for Santa Claus. This factor also compares against a natural, compact LP for Santa Claus.

Feb
13
Wed
[Theory Seminar] Martin Farach-Colton
Feb 13 @ 12:00 pm – 1:00 pm

Speaker: Martin Farach-Colton
Affiliation: Rutgers University

Title: TBA

Abstract: TBA