Shengminjie Chen

A Deterministic $0.401$-Approximation for Non-monotone Submodular Maximization under Matroid Constraints

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, w...