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^{\prime }$ 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.