A Deterministic $0.401$-Approximation for Non-monotone Submodular Maximization under Matroid Constraints
Abstract
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−ε) \cite{ChenGLSZ2026}. Our algorithm builds on the extended multilinear extension and provides a deterministic implementation of the recursive guided framework underlying the randomized $0.401$-approximation algorithm. The main technical ingredient is a direction oracle supported on at most two partitioned matroid bases. This oracle simultaneously satisfies the growth condition required by the extended-multilinear update and an approximate stationarity condition needed to construct the recursive guides. The resulting finite-support representation enables exact evaluation of the relevant expectations and marginal values without random sampling. The algorithm uses polynomially many value- and independence-oracle queries.
Related
- An Analytic 0.48-Approximation for Non-Monotone k-Submodular Maximization under a Matroid Constraint
- Geometry-Dependent Approximation for Non-Monotone k-Submodular Maximization
- Online Non-Monotone DR-Submodular Maximization Matching the Offline $0.401$ Factor
- Dec-BFTRL: Squre-Root Regret for Decentralized Online Upper-Linearizable Optimization under Separation Access with Application to Continuous Submodular Maximization
- On Exact Dual and Mixed-Integer Reformulations for Finite Horizon Markov Decision Processes with Submodular Revenue Maximization
BibTeX
@misc{chen2026deterministic,
title = {{A Deterministic $0.401$-Approximation for Non-monotone Submodular Maximization under Matroid Constraints}},
author = {Shengminjie Chen and Kaifeng Lin and Xiaoming Sun and Jialin Zhang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.16785},
eprint = {2610.16785},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.16785},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - A Deterministic $0.401$-Approximation for Non-monotone Submodular Maximization under Matroid Constraints
AU - Shengminjie Chen
AU - Kaifeng Lin
AU - Xiaoming Sun
AU - Jialin Zhang
PY - 2026
DA - 2026/10/12
PB - arXiv
DO - 10.48550/arxiv.2610.16785
UR - https://arxiv.org/abs/2610.16785
AB - 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−ε) \cite{ChenGLSZ2026}. Our algorithm builds on the extended multilinear extension and provides a deterministic implementation of the recursive guided framework underlying the randomized $0.401$-approximation algorithm. The main technical ingredient is a direction oracle supported on at most two partitioned matroid bases. This oracle simultaneously satisfies the growth condition required by the extended-multilinear update and an approximate stationarity condition needed to construct the recursive guides. The resulting finite-support representation enables exact evaluation of the relevant expectations and marginal values without random sampling. The algorithm uses polynomially many value- and independence-oracle queries.
ER -