Computer Science/Discrete Mathematics Seminar I

Two (More) Algorithms for Set Cover

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 approaches to get similar guarantees, which arose from trying to get refined guarantees for the problem 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).

Date & Time

March 06, 2023 | 11:15am – 12:15pm


Simonyi 101 and Remote Access


Anupam Gupta

Speaker Affiliation

Carnegie Mellon University