Stronger Approximation Guarantees for Non-Monotone γ-Weakly DR-Submodular Maximization

arXiv (Cornell University) 2026 Preprint Open access

Read full text
Authors: Hareshkumar Jadav, Ranveer Singh, Vaneet Aggarwal
Cited by: 0

Abstract

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 $γ

Fields of Study & Subjects

Complexity and Algorithms in Graphs Stochastic Gradient Optimization Techniques Risk and Portfolio Optimization

Publication details

Journal / source
arXiv (Cornell University)
Publication date
2 January 2026
Document type
Preprint