Stronger Approximation Guarantees for Non-Monotone γ-Weakly DR-Submodular Maximization
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_ | 1866914230329933824 |
|---|---|
| author | Jadav, Hareshkumar Singh, Ranveer Aggarwal, Vaneet |
| author_facet | Jadav, Hareshkumar Singh, Ranveer Aggarwal, Vaneet |
| contents | Maximizing submodular objectives under constraints is a fundamental problem in machine learning and optimization. We study the maximization of a nonnegative, non-monotone $γ$-weakly DR-submodular function over a down-closed convex body. Our main result is an approximation algorithm whose guarantee depends smoothly on $γ$; in particular, when $γ=1$ (the DR-submodular case) our bound recovers the $0.401$ approximation factor, while for $γ<1$ the guarantee degrades gracefully and, it improves upon previously reported bounds for $γ$-weakly DR-submodular maximization under the same constraints. Our approach combines a Frank-Wolfe-guided continuous-greedy framework with a $γ$-aware double-greedy step, yielding a simple yet effective procedure for handling non-monotonicity. This results in state-of-the-art guarantees for non-monotone $γ$-weakly DR-submodular maximization over down-closed convex bodies. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_00611 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Stronger Approximation Guarantees for Non-Monotone γ-Weakly DR-Submodular Maximization Jadav, Hareshkumar Singh, Ranveer Aggarwal, Vaneet Machine Learning Artificial Intelligence Computational Complexity Optimization and Control Maximizing submodular objectives under constraints is a fundamental problem in machine learning and optimization. We study the maximization of a nonnegative, non-monotone $γ$-weakly DR-submodular function over a down-closed convex body. Our main result is an approximation algorithm whose guarantee depends smoothly on $γ$; in particular, when $γ=1$ (the DR-submodular case) our bound recovers the $0.401$ approximation factor, while for $γ<1$ the guarantee degrades gracefully and, it improves upon previously reported bounds for $γ$-weakly DR-submodular maximization under the same constraints. Our approach combines a Frank-Wolfe-guided continuous-greedy framework with a $γ$-aware double-greedy step, yielding a simple yet effective procedure for handling non-monotonicity. This results in state-of-the-art guarantees for non-monotone $γ$-weakly DR-submodular maximization over down-closed convex bodies. |
| title | Stronger Approximation Guarantees for Non-Monotone γ-Weakly DR-Submodular Maximization |
| topic | Machine Learning Artificial Intelligence Computational Complexity Optimization and Control |
| url | https://arxiv.org/abs/2601.00611 |