Stable Max Coverage Under a Cardinality Constraint

We propose a stable algorithm for solving maximum coverage problems under a cardinality constraint of $k$ in a record-level stability model, where adjacent instances $I\sim I'$ differ by the incidence of one universe element. Our algorithm computes a negative-entropy-regularized maximizer of the capped concave relaxation over the hypersimplex and rounds it with a common-seed rounding map from hypersimplex correlated sampling. The resulting sensitivity bound is $\min\{2k, \alpha_k k/\lambda\}$, where $\lambda$ is the regularization parameter and $\alpha_k = O(\log k)$. For utility, the expected coverage has approximation factor $1-\frac{1}{e}$ with an additive error of order $O(\lambda k \log \frac{m}{k})$, where $m$ is the number of input sets. We also report experiments on synthetic and real-world instances.