{"id":"arxiv/2601.00611","url":"https://arxiv.org/abs/2601.00611","tags":["cs.LG","cs.AI","cs.CC","math.OC"],"score":0,"title":"Stronger Approximation Guarantees for Non-Monotone γ-Weakly DR-Submodular Maximization","domain":"cs.LG","source":"arxiv","authors":["Hareshkumar Jadav","Ranveer Singh","Vaneet Aggarwal"],"reviews":0,"subject":"cs.LG","summary":"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.…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-01-02","reactions":{}}