On the Average-Case Performance of Greedy for Maximum Coverage
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913066876141568 |
|---|---|
| author | Balkanski, Eric Chatzitheodorou, Jason Sentenac, Flore |
| author_facet | Balkanski, Eric Chatzitheodorou, Jason Sentenac, Flore |
| contents | For the classical maximum coverage problem, the greedy algorithm achieves a worst-case $1-1/e$ approximation, which is optimal unless $\text{P} = \text{NP}$. The notion of coverage appears in a wide range of optimization tasks, where empirical evaluations indicate approximation ratios close to $1$ for the greedy algorithm on real data. Random models have provided average-case justifications for the empirical performance of many well-known algorithms, but little is known about the average-case performance of greedy for maximum coverage. We analyze the expected approximation ratio of the greedy algorithm in a random model, which we call the left-regular random model. We first show that, for all parameter settings of this model, the expected approximation ratio of the greedy algorithm improves by a constant over its worst-case $1-1/e$ guarantee. We then identify two simple conditions, either of which ensures that the expected approximation ratio is close to $1$ for sufficiently large graphs. Finally, we show that there is a regime where greedy does not achieve an expected approximation better than $0.94$. To obtain these results, we develop analytical tools, including a novel application of the differential equation method and a connection to maximum matching in Erdős-Rényi graphs, which may be of independent interest for other random models. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_24884 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | On the Average-Case Performance of Greedy for Maximum Coverage Balkanski, Eric Chatzitheodorou, Jason Sentenac, Flore Data Structures and Algorithms 05C80 (Primary), 68W40, 68Q25, 60C05, 68W25 F.2.2; G.2.2; G.3 For the classical maximum coverage problem, the greedy algorithm achieves a worst-case $1-1/e$ approximation, which is optimal unless $\text{P} = \text{NP}$. The notion of coverage appears in a wide range of optimization tasks, where empirical evaluations indicate approximation ratios close to $1$ for the greedy algorithm on real data. Random models have provided average-case justifications for the empirical performance of many well-known algorithms, but little is known about the average-case performance of greedy for maximum coverage. We analyze the expected approximation ratio of the greedy algorithm in a random model, which we call the left-regular random model. We first show that, for all parameter settings of this model, the expected approximation ratio of the greedy algorithm improves by a constant over its worst-case $1-1/e$ guarantee. We then identify two simple conditions, either of which ensures that the expected approximation ratio is close to $1$ for sufficiently large graphs. Finally, we show that there is a regime where greedy does not achieve an expected approximation better than $0.94$. To obtain these results, we develop analytical tools, including a novel application of the differential equation method and a connection to maximum matching in Erdős-Rényi graphs, which may be of independent interest for other random models. |
| title | On the Average-Case Performance of Greedy for Maximum Coverage |
| topic | Data Structures and Algorithms 05C80 (Primary), 68W40, 68Q25, 60C05, 68W25 F.2.2; G.2.2; G.3 |
| url | https://arxiv.org/abs/2604.24884 |