Breaking Barriers: Combinatorial Algorithms for Non-monotone Submodular Maximization with Sublinear Adaptivity and $1/e$ Approximation
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866916991179161600 |
|---|---|
| author | Chen, Yixin Chen, Wenjing Kuhnle, Alan |
| author_facet | Chen, Yixin Chen, Wenjing Kuhnle, Alan |
| contents | With the rapid growth of data in modern applications, parallel algorithms for maximizing non-monotone submodular functions have gained significant attention. In the parallel computation setting, the state-of-the-art approximation ratio of $1/e$ is achieved by a continuous algorithm (Ene & Nguyen, 2020) with adaptivity $ O\left(\log(n)\right)$. In this work, we focus on size constraints and present the first combinatorial algorithm matching this bound -- a randomized parallel approach achieving $1/e-\varepsilon$ approximation ratio. This result bridges the gap between continuous and combinatorial approaches for this problem. As a byproduct, we also develop a simpler $(1/4-\varepsilon)$-approximation algorithm with high probability ($\ge 1-1/n$). Both algorithms achieve $ O\left(\log(n)\log(k)\right)$ adaptivity and $O\left(n\log(n)\log(k)\right)$ query complexity. Empirical results show our algorithms achieve competitive objective values, with the $(1/4-\varepsilon)$-approximation algorithm particularly efficient in queries. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_07062 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Breaking Barriers: Combinatorial Algorithms for Non-monotone Submodular Maximization with Sublinear Adaptivity and $1/e$ Approximation Chen, Yixin Chen, Wenjing Kuhnle, Alan Data Structures and Algorithms With the rapid growth of data in modern applications, parallel algorithms for maximizing non-monotone submodular functions have gained significant attention. In the parallel computation setting, the state-of-the-art approximation ratio of $1/e$ is achieved by a continuous algorithm (Ene & Nguyen, 2020) with adaptivity $ O\left(\log(n)\right)$. In this work, we focus on size constraints and present the first combinatorial algorithm matching this bound -- a randomized parallel approach achieving $1/e-\varepsilon$ approximation ratio. This result bridges the gap between continuous and combinatorial approaches for this problem. As a byproduct, we also develop a simpler $(1/4-\varepsilon)$-approximation algorithm with high probability ($\ge 1-1/n$). Both algorithms achieve $ O\left(\log(n)\log(k)\right)$ adaptivity and $O\left(n\log(n)\log(k)\right)$ query complexity. Empirical results show our algorithms achieve competitive objective values, with the $(1/4-\varepsilon)$-approximation algorithm particularly efficient in queries. |
| title | Breaking Barriers: Combinatorial Algorithms for Non-monotone Submodular Maximization with Sublinear Adaptivity and $1/e$ Approximation |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2502.07062 |