Seminar: Anupam Gupta (Carnegie Mellon University)

Speaker: Anupam Gupta (Carnegie Mellon University)


Two (More) Algorithms for Set Cover

Zoom link:
(Meeting ID: 849 0964 5595, Passcode: 772448)


In the minimum cost set cover problem, a set system is given as input, and
the goal is to find a collection of sets with minimum cost whose union
covers the universe. This NP-hard problem has long been known to admit
logarithmic approximations. Moreover, the logarithmic guarantee is tight,
unless P=NP. In this talk I will present two new algorithms which also get
logarithmic guarantees. These algorithms came out of attempts to get
refined guarantees for set cover in beyond-worst-case settings.

The talk is based on joint works with Greg Kehne (CMU and Harvard),
Euiwoong Lee (U. Michigan), Roie Levin (CMU and Tel Aviv U), and Jason Li
(CMU and Simons/Berkeley).