Maximum coverage: classical and new results

Title:Maximum coverage: classical and new results
Host Faculty: Dr.Nitin Saurabh
Speaker: Prof. Yuval Filmus
Date: 28 August
Time: 11:00 am
Venue: CSE Seminar Hall

Abstract

Maximum coverage is a classical optimization problem, already appearing in Karp’s 1972 foundational paper. We will start by discussing some classical stuff: NP-hardness, approximation algorithms, inapproximability (no background will be assumed). We will then describe our work on “dense maximum coverage”, highlighting some open questions.

Joint work with Roy Schwartz (Technion) and Alexander V. Smal (JetBrains).

Bio

Prof. Yuval Filmus is a faculty in the Computer Science Department at Technion, Israel. Before joining as a faculty he did his PhD from the University of Toronto and was a postdoc at the IAS, Princeton. He is a recipient of the Alon Fellowship and the Krill Prize. His research interests are quite broad which includes, among other things, Boolean function analysis, Combinatorics, Computational Complexity, Submodular optimization, Proof Complexity, Approximation Algorithms, Social Choice Theory, etc.