Dutch Seminar on Optimization (N&O)

Dutch Seminar on Optimization with Anupam Gupta (Carnegie Mellon University)

Speaker: Anupam Gupta (Carnegie Mellon University)
Title: Two (More) Algorithms for Set Cover

The meeting will take place virtually here:
https://cwi-nl.zoom.us/j/84909645595?pwd=b1M4QnNKVzNMdmNSVFNaZUJmR1kvUT09
(Meeting ID: 849 0964 5595, Passcode: 772448)

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