Conditionally Tight Algorithms for Maximum k-Coverage and Partial k-Dominating Set via Arity-Reducing Hypercuts

Nick Fischer, Marvin Künnemann, Mirza Redzic

We revisit the classic Maximum $k$-Coverage problem: Determine the largest number $t$ of elements that can be covered by choosing $k$ sets from a given family $\mathcal{F} = \{S_1,…