Events by date

Title: Stochastic Probing with Applications

Speaker: David Kalichman Affiliation: University of Waterloo Location: MC 6029 or contact Rian Neogi for the Zoom link

Abstract: We will explore a stochastic probing problem. Given a set of elements which have weights and independent probabilities of being "active," the goal is to construct a subset of active elements of maximum weight. To form such a set, we must "probe" elements sequentially to determine whether they are active.

Title: The Integrality Gap for the Santa Claus Problem

Speaker: Penny Haxell Affiliation: University of Waterloo Location: MC 5501 or contact Melissa Cambridge for Zoom link

Abstract: 

In the max-min allocation problem, a set of players are to be allocated disjoint subsets of a set of   indivisible resources, such that the minimum utility among all players is maximized.  In the restricted variant, also known as the Santa Claus Problem,  each resource (``toy'') has an intrinsic positive value, and each player (``child'') covets a subset of the resources. Thus Santa wants to distribute the toys amongst the children, while (to satisfy
jealous parents?) wishing to maximize the minimum total value of toys received by each child. This problem turns out to have a natural reformulation in terms of hypergraph matching.