License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2021.9
URN: urn:nbn:de:0030-drops-136543
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/13654/
Barman, Siddharth ;
Fawzi, Omar ;
Fermé, Paul
Tight Approximation Guarantees for Concave Coverage Problems
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 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 φ, 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 NP-hardness result when φ grows in a sublinear way.
As special cases, we improve the result of [Siddharth Barman et al., 2020] about maximum multi-coverage, that was based on the unique games conjecture, and we recover the result of [Szymon Dudycz et al., 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.
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:1--9:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-180-1},
ISSN = {1868-8969},
year = {2021},
volume = {187},
editor = {Bl\"{a}ser, Markus and Monmege, Benjamin},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/13654},
URN = {urn:nbn:de:0030-drops-136543},
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 |
