Tight Approximation Guarantees for Concave Coverage Problems (STACS 2021)

Abstract

In the maximum coverage problem, we are given subsets $T_1, \ldots, T_m$ of a universe $[n]$ along with an integer $k$ and the objective is to find a subset $S \subseteq [m]$ of size $k$ that maximizes $C(S) := |\bigcup_{i \in S} T_i|$. It is a classic result that the greedy algorithm for this problem achieves an optimal approximation ratio of $1-e^{-1}$.

In this work we consider a generalization of this problem wherein an element $a$ can contribute by an amount that depends on the number of times it is covered. Given a concave, nondecreasing function $\varphi$, we define $C^{\varphi}(S) := \sum_{a \in [n]} w_{\varphi(|S|^a)}$, where $|S|^a = |{i \in S : a \in T_i}|$. The standard maximum coverage problem corresponds to taking $\varphi(j) = \min(j,1)$. For any such $\varphi$, we provide an efficient algorithm that achieves an approximation ratio equal to the Poisson concavity ratio of $\varphi$, defined by $\alpha_{\varphi} := \min_{x \in \mathbb{N}^*} \frac{E[\varphi(Poi(x))]}{\varphi(E[Poi(x)])}$. Complementing this approximation guarantee, we establish a matching NP-hardness result when $\varphi$ grows in a sublinear way.

As special cases, we improve the result of Barman et al., IPCO, 2020 about maximum multi-coverage, that was based on the unique games conjecture, and we recover the result of Dudycz et al., IJCAI, 2020 on multi-winner approval-based voting for geometrically dominant rules. Our result goes beyond these special cases and we illustrate it with applications to distributed resource allocation problems, welfare maximization problems and approval-based voting for general rules.

Publication
38th International Symposium on Theoretical Aspects of Computer Science, STACS 2021, March 16-19, 2021, Saarbrücken, Germany

Related