Seminars
View all Seminars | Download ICal for this eventFrom Max Coverage to Multiwinner Elections: A Parameterized Approximation Perspective
Series: Bangalore Theory Seminars
Speaker: Souvik Saha, The Institute of Mathematical Science, Chennai
Date/Time: Apr 22 16:00:00
Location: CSA Seminar Hall (Room No. 254, First Floor)
Abstract:
In the classical Max Coverage problem, the goal is to select $k$ sets from a given set system to maximize the number of covered elements. This problem famously admits a polynomial-time $(1-1/e)$-approximation??a ratio that, under the Gap-ETH, cannot be improved even by algorithms running in time $f(k,varepsilon)cdot n^{o(k)}$. Driven by these stringent lower bounds, the problem has recently seen a surge of interest from the perspective of parameterized approximation. In this talk, we will explore how the multiwinner election problem serves as a natural generalization of Max Coverage. In this setting, we are given a set of voters with approval preferences over candidates, and the objective is to choose a committee of $k$ candidates that maximizes overall voter satisfaction, as defined by Thiele scoring rules. Building on this connection, we will discuss recent results on the fixed-parameter approximability of these multiwinner voting rules.
Microsoft Teams link:
Link
We are grateful to the Kirani family (Link and the Walmart Center for Tech Excellence (Link for generously supporting this seminar series
Hosts: Rameesh Paul, Debajyoti Kar, KVN Sreenivas, Nirjhar Das, Rahul Madhavan