{"id":"arxiv/2610.16785","url":"https://arxiv.org/abs/2610.16785","tags":["cs.DS","math.OC"],"score":0,"title":"A Deterministic $0.401$-Approximation for Non-monotone Submodular Maximization under Matroid Constraints","domain":"cs.DS","source":"arxiv","authors":["Shengminjie Chen","Kaifeng Lin","Xiaoming Sun","Jialin Zhang"],"reviews":0,"subject":"cs.DS","summary":"Submodular maximization arises in a wide range of combinatorial optimization problems and has been extensively studied from the perspective of approximation algorithms. For maximizing nonnegative, non-monotone submodular functions subject to a matroid constraint, randomized algorithms achieve a $0.401$-approximation, whereas obtaining comparable deterministic guarantees remains challenging. In this paper, we present a deterministic $0.401$-approximation algorithm in the exact value and independence oracle model, improving upon the previous deterministic guarantee of $(0.385-\\varepsilon)$…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-10-12","reactions":{}}