Seminars

View all Seminars  |  Download ICal for this event

Multiple Covering Constraints: Geometry to Submodularity

Series: Bangalore Theory Seminars

Speaker: Prof. Chandra Chekuri University of Illinois, Urbana-Champaign

Date/Time: Jul 07 11:00:00

Location: CSA Auditorium, (Room No. 104, Ground Floor)

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 that are joint work with several co-authors that
will be mentioned in the talk.


Microsoft teams link:

Link


We are grateful to the Kirani family (Link and the Walmart Center for Tech Excellence (Link for generously supporting this seminar series


Hosts: Rameesh Paul, KVN Sreenivas, Rahul Madhavan, Debajyoti Kar, Nirjhar Das