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 $k$ and maximizes coverage; the latter meets a target with as few…