Separating Coverage and Submodular: Maximization Subject to a Cardinality Constraint
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866913755789524992 |
|---|---|
| author | Filmus, Yuval Schwartz, Roy Smal, Alexander V. |
| author_facet | Filmus, Yuval Schwartz, Roy Smal, Alexander V. |
| contents | We consider two classic problems: maximum coverage and monotone submodular maximization subject to a cardinality constraint. [Nemhauser--Wolsey--Fisher '78] proved that the greedy algorithm provides an approximation of $1-1/e$ for both problems, and it is known that this guarantee is tight ([Nemhauser--Wolsey '78; Feige '98]). Thus, one would naturally assume that everything is resolved when considering the approximation guarantees of these two problems, as both exhibit the same tight approximation and hardness.
In this work we show that this is not the case, and study both problems when the cardinality constraint is a constant fraction $c \in (0,1]$ of the ground set. We prove that monotone submodular maximization subject to a cardinality constraint admits an approximation of $1-(1-c)^{1/c}$; This approximation equals $1$ when $c=1$ and it gracefully degrades to $1-1/e$ when $c$ approaches $0$. Moreover, for every $c=1/s$ (for any integer $s \in \mathbb{N}$) we present a matching hardness.
Surprisingly, for $c=1/2$ we prove that Maximum Coverage admits an approximation of $0.7533$, thus separating the two problems. To the best of our knowledge, this is the first known example of a well-studied maximization problem for which coverage and monotone submodular objectives exhibit a different best possible approximation. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_05553 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Separating Coverage and Submodular: Maximization Subject to a Cardinality Constraint Filmus, Yuval Schwartz, Roy Smal, Alexander V. Data Structures and Algorithms 68W25 F.2.2 We consider two classic problems: maximum coverage and monotone submodular maximization subject to a cardinality constraint. [Nemhauser--Wolsey--Fisher '78] proved that the greedy algorithm provides an approximation of $1-1/e$ for both problems, and it is known that this guarantee is tight ([Nemhauser--Wolsey '78; Feige '98]). Thus, one would naturally assume that everything is resolved when considering the approximation guarantees of these two problems, as both exhibit the same tight approximation and hardness. In this work we show that this is not the case, and study both problems when the cardinality constraint is a constant fraction $c \in (0,1]$ of the ground set. We prove that monotone submodular maximization subject to a cardinality constraint admits an approximation of $1-(1-c)^{1/c}$; This approximation equals $1$ when $c=1$ and it gracefully degrades to $1-1/e$ when $c$ approaches $0$. Moreover, for every $c=1/s$ (for any integer $s \in \mathbb{N}$) we present a matching hardness. Surprisingly, for $c=1/2$ we prove that Maximum Coverage admits an approximation of $0.7533$, thus separating the two problems. To the best of our knowledge, this is the first known example of a well-studied maximization problem for which coverage and monotone submodular objectives exhibit a different best possible approximation. |
| title | Separating Coverage and Submodular: Maximization Subject to a Cardinality Constraint |
| topic | Data Structures and Algorithms 68W25 F.2.2 |
| url | https://arxiv.org/abs/2411.05553 |