Fast Approximation Algorithm for Non-Monotone DR-submodular Maximization under Size Constraint
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866914134042345472 |
|---|---|
| author | Tran, Tan D. Pham, Canh V. |
| author_facet | Tran, Tan D. Pham, Canh V. |
| contents | This work studies the non-monotone DR-submodular Maximization over a ground set of $n$ subject to a size constraint $k$. We propose two approximation algorithms for solving this problem named FastDrSub and FastDrSub++. FastDrSub offers an approximation ratio of $0.044$ with query complexity of $O(n \log(k))$. The second one, FastDrSub++, improves upon it with a ratio of $1/4-ε$ within query complexity of $(n \log k)$ for an input parameter $ε>0$. Therefore, our proposed algorithms are the first constant-ratio approximation algorithms for the problem with the low complexity of $O(n \log(k))$.
Additionally, both algorithms are experimentally evaluated and compared against existing state-of-the-art methods, demonstrating their effectiveness in solving the Revenue Maximization problem with DR-submodular objective function. The experimental results show that our proposed algorithms significantly outperform existing approaches in terms of both query complexity and solution quality. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_02254 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Fast Approximation Algorithm for Non-Monotone DR-submodular Maximization under Size Constraint Tran, Tan D. Pham, Canh V. Data Structures and Algorithms Artificial Intelligence Computational Complexity This work studies the non-monotone DR-submodular Maximization over a ground set of $n$ subject to a size constraint $k$. We propose two approximation algorithms for solving this problem named FastDrSub and FastDrSub++. FastDrSub offers an approximation ratio of $0.044$ with query complexity of $O(n \log(k))$. The second one, FastDrSub++, improves upon it with a ratio of $1/4-ε$ within query complexity of $(n \log k)$ for an input parameter $ε>0$. Therefore, our proposed algorithms are the first constant-ratio approximation algorithms for the problem with the low complexity of $O(n \log(k))$. Additionally, both algorithms are experimentally evaluated and compared against existing state-of-the-art methods, demonstrating their effectiveness in solving the Revenue Maximization problem with DR-submodular objective function. The experimental results show that our proposed algorithms significantly outperform existing approaches in terms of both query complexity and solution quality. |
| title | Fast Approximation Algorithm for Non-Monotone DR-submodular Maximization under Size Constraint |
| topic | Data Structures and Algorithms Artificial Intelligence Computational Complexity |
| url | https://arxiv.org/abs/2511.02254 |