Max Coverage is a classical NP-hard problem that remains hard to approximate, even in fixed-parameter tractable (FPT) time. In this talk, we will discuss the FPT approximation algorithms for Max Coverage and related problems, under certain structural restrictions on the set family. Notably, Max Coverage is equivalent to the well-known Chamberlin–Courant rule in multiwinner voting, which seeks to select a representative committee based on voters' preferences. In this talk, we will discuss the recent advances in FPT approximation algorithms for a broad class of voting rules that generalize the Chamberlin–Courant rule.
The talk is based on the following two papers.
(1) Parameterized Approximation Algorithms for MAX-SAT with Cardinality Constraint and Maximum Coverage, L. Kanesh, P. Jain, F. Panolan, S. Saha, A. Sahu, S. Saurabh, and A. Upasana, SODA 2023.
(2) More Efforts Towards Fixed-Parameter Approximability of Multiwinner Rules, S. Gupta, P. Jain, S. Saha, S. Saurabh, and A. Upasana, accepted in IJCAI 2025.
Short Bio:
Pallavi Jain is an Assistant Professor at the Indian Institute of Technology Jodhpur. She is a theoretical computer scientist with research interests in Computational Social Choice Theory, a field at the intersection of Economics and Computer Science, Graph Algorithms, and Parameterized Complexity. Most of her current work centers on modeling real-world problems that involve collective decision-making, with a particular focus on fairness and efficiency. She explores both the classical and parameterized complexity of these problems.
Before joining IIT Jodhpur, Pallavi was a postdoctoral fellow at Ben-Gurion University of the Negev, Israel. She also held a SERB-NPDF position at the Institute of Mathematical Sciences, Chennai. She obtained her Ph.D. from Dayalbagh Educational Institute, Agra.
