Showing cs.DSShow all
2 papers · 1 filter
cs.DS2026
Parameterized Approximation of Max k-Weight CSP: A Dichotomy for Boolean Languages
Rudranarayan Kar, Souvik Saha, Abhishek Sahu
We study \textsc{Max -Weight CSP}: maximize the satisfied weight of Boolean constraints with nonnegative rational weights by setting at most variables to . Each constrain…
cs.DS2026
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…