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).