The theory seminar next Monday will be given by Chandra Chekuri (UIUC). Details below.
Abstract: Suppose we are given a set of points in the plane and a collection of (weighted) disks and we wish to cover the points with a minimum weight sub-collection of the given disks. This is an instance of geometric set cover and admits a constant factor approximation via the non-trivial technique of quasi-uniform sampling of Varadarajan that was refined by Chan et al; this is in contrast to the logarithmic factor hardness for general set cover. In this talk we consider generalizations and variants of set cover where the points are colored/grouped into r sets and each color i has a requirement k_i --- the goal is to cover at least k_i points from each color i. The single color case is already interesting and is the partial set cover problem. We build on work of Inamdar and Varadarajan and that of Har-Peled and Jones, bring the lens of submodularity to bear on these problems, and outline several results and applications to geometric set cover problems, facility location, fairness and others.
Based on two papers. An older one https://link.springer.com/article/10.1007/s10878-022-00874-x
and a more recent one https://arxiv.org/abs/2507.09879