5 papers
Fixed Budget vs. Covering Target: The Partial Set Cover Boundary for Bounded VC-Dimension
Madhumita Kundu, Souvik Saha, Saket Saurabh +1
Maximum Coverage and Partial Set Cover are fundamental parameterized covering problems. The former fixes a budget and maximizes coverage; the latter meets a target with as few…
Dominating Set with Quotas: Balancing Coverage and Constraints
Sobyasachi Chatterjee, Sushmita Gupta, Saket Saurabh +2
We study a natural generalization of the classical \textsc{Dominating Set} problem, called \textsc{Dominating Set with Quotas} (DSQ). In this problem, we are given a graph \( G \),…
Line Cover and Related Problems
Matthias Bentert, Fedor v. Fomin, Petr A. Golovach +4
We study extensions of the classic \emph{Line Cover} problem, which asks whether a set of points in the plane can be covered using lines. Line Cover is known to be NP-hard,…
More Efforts Towards Fixed-Parameter Approximability of Multiwinner Rules
Sushmita Gupta, Pallavi Jain, Souvik Saha +2
Multiwinner Elections have emerged as a prominent area of research with numerous practical applications. We contribute to this area by designing parameterized approximation algorit…
Satisfiability to Coverage in Presence of Fairness, Matroid, and Global Constraints
Tanmay Inamdar, Pallavi Jain, Daniel Lokshtanov +3
In MaxSAT with Cardinality Constraint problem (CC-MaxSAT), we are given a CNF-formula , and , and the goal is to find an assignment with at most variables set…