Abstract
In the maximum coverage problem, we are given subsets T_1, …, T_m of a universe [n] along with an integer k and the objective is to find a subset S ⊆ [m] of size k that maximizes C(S) : = ⋃_{i ∈ S} T_i. It is a classic result that the greedy algorithm for this problem achieves an optimal approximation ratio of 1e^{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 φ, we define C^{φ}(S) := ∑_{a ∈ [n]}w_aφ(S_a), where S_a = {i ∈ S : a ∈ T_i}. The standard maximum coverage problem corresponds to taking φ(j) = min{j,1}. For any such φ, we provide an efficient algorithm that achieves an approximation ratio equal to the Poisson concavity ratio of φ, defined by α_{φ} : = min_{x ∈ ℕ^*} ?[φ(Poi(x))] / φ(?[Poi(x)]). Complementing this approximation guarantee, we establish a matching NPhardness result when φ grows in a sublinear way.
As special cases, we improve the result of [Siddharth Barman et al., 2020] about maximum multicoverage, that was based on the unique games conjecture, and we recover the result of [Szymon Dudycz et al., 2020] on multiwinner approvalbased 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 approvalbased voting for general rules.
BibTeX  Entry
@InProceedings{barman_et_al:LIPIcs.STACS.2021.9,
author = {Barman, Siddharth and Fawzi, Omar and Ferm\'{e}, Paul},
title = {{Tight Approximation Guarantees for Concave Coverage Problems}},
booktitle = {38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)},
pages = {9:19:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771801},
ISSN = {18688969},
year = {2021},
volume = {187},
editor = {Bl\"{a}ser, Markus and Monmege, Benjamin},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/13654},
URN = {urn:nbn:de:0030drops136543},
doi = {10.4230/LIPIcs.STACS.2021.9},
annote = {Keywords: Approximation Algorithms, Coverage Problems, Concave Function}
}
Keywords: 

Approximation Algorithms, Coverage Problems, Concave Function 
Collection: 

38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021) 
Issue Date: 

2021 
Date of publication: 

10.03.2021 