Seminar: Anupam Gupta (Carnegie Mellon University)
- https://wsc.project.cwi.nl/dutch-optimization-seminar/events/seminar-anupam-gupta-carnegie-mellon-university
- Seminar: Anupam Gupta (Carnegie Mellon University)
- 2023-05-23T16:00:00+02:00
- 2023-05-23T17:00:00+02:00
- When May 23, 2023 from 04:00 PM to 05:00 PM (Europe/Amsterdam / UTC200)
- Where Online seminar
- Contact Name Daniel Dadush, Cedric Koh, and Sven Polak
- Web Visit external website
-
Add event to calendar
iCal
Speaker: Anupam Gupta (Carnegie Mellon University)
Title:
Two (More) Algorithms for Set Cover
Zoom link:
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).
Video:
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).
Video:
Slides: