Tight Approximation Guarantees for Concave Coverage Problems

Siddharth Barman, Omar Fawzi, Paul Fermé

In the maximum coverage problem, we are given subsets $T_1,\dots ,T_m$ of a universe $[n]$ along with an integer $k$ and the objective is to find a subset $S\subseteq [m]$ of si…