Deterministic Algorithm for Non-monotone Submodular Maximization under Matroid and Knapsack Constraints

Shengminjie Chen, Yiwei Gao, Kaifeng Lin, Xiaoming Sun, Jialin Zhang · 2026

Read Deterministic Algorithm for Non-monotone Submodular Maximization under Matroid and Knapsack Constraints by Shengminjie Chen, Yiwei Gao, Kaifeng Lin, Xiaoming Sun, Jialin Zhang (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-11996.txt.

Introduction

Chen, Gao, Lin, Sun, and Zhang give deterministic algorithms for a hard maximization problem. The task is to maximize a non-monotone submodular function under matroid or knapsack constraints. Most strong methods for this task are randomized, which leaves some doubt in each run. Their approach builds on an extended multilinear extension framework. For both constraint types, the new ratios beat the best deterministic ratios known before. Both methods also run with polynomial query cost in the size of the ground set.

Catalog record

CREATORShengminjie Chen, Yiwei Gao, Kaifeng Lin, Xiaoming Sun, Jialin Zhang
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE94602
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.11996

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Deterministic Algorithm for Non-monotone Submodular Maximization under Matroid and Knapsack Constraints Thanks: Alphabetical Order. Corresponding Author: Shengminjie Chen, [email protected] Shengminjie Chen, Yiwei Gao, Kaifeng Lin, Xiaoming Sun, Jialin Zhang Abstract Submodular maximization constitutes a prominent research topic in combinatorial optimization and theoretical computer science, with extensive applications across diverse domains. While substantial advancements have been achieved in approximation algorithms for submodular maximization, the majority of algorithms yielding high approximation guarantees are randomized. In this work, we investigate deterministic approximation algorithms for maximizing non-monotone submodular functions subject to matroid and knapsack constraints. For the two distinct constraint settings, we propose novel deterministic algorithms grounded in an extended multilinear extension framework. For matroid constraints, our algorithm achieves an approximation ratio of ( 0.385 − ε ) (0.385-\varepsilon) , while for knapsack constraints, the proposed algorithm attains an approximation ratio of ( 0.367 − ε ) (0.367-\varepsilon) . Both algorithms run in poly ⁡ ( n ) \mathrm{poly}(n) value queries, where n n is the size of the ground set, and improve upon the state-of-the-art deterministic approximation ratios of ( 0.367 − ε ) (0.367-\varepsilon) for matroid constraints and 0.25 0.25 for knapsack constraints. 1 Introduction Submodularity, capturing the principle of diminishing returns, naturally arises in many functions of theoretical interest and provides a powerful abstraction for many subset selection problems such as game theory [ 21 , 20 , 19 ] , maximal social welfare [ 26 , 35 , 32 ] , influence maximization [ 36 , 16 , 31 ] , facility location [ 1 , 2 ] , data summarization [ 40 , 41 , 45 ] , etc. Maximizing submodular functions subject to various constraints, due to the \mathcal{NP} -hard property, is a fundamental problem that has been extensively studied in both operations research and theoretical computer science, playing a central role in combinatorial optimization and approximation algorithms. Formally, for a ground set \mathcal{N} , the submodular function f:2^{\mathcal{N}}\rightarrow\mathbb{R} defined on \mathcal{N} satisfies the following property: for any subset A\subseteq B\subseteq\mathcal{N} and any element u\in\mathcal{N}\setminus B , f(A\cup\{u\})-f(A)\geq f(B\cup\{u\})-f(B). Equivalently, a function f is submodular if and only if for any sets S,T\subseteq\mathcal{N} , f(S)+f(T)\geq f(S\cup T)+f(S\cap T). The systematic study of submodular maximization dates back to 1978, when Nemhauser et al. [ 37 ] abstracted the concept of submodularity from various combinatorial problems and established the 1-1/e approximation ratio for monotone functions via a greedy algorithm. Since then, numerous combinatorial algorithms have been developed, particularly for cardinality constraints [ 42 , 38 , 6 ] , knapsack constraints [ 44 , 34 , 3 , 25 , 33 ] , matroid constraints [ 27 , 5 , 30 ] , and the unconstrained case [ 7 , 39 ] . A significant advancement came with the introduction of the multilinear extension framework by Vondrák [ 46 ] . This framework extends a discrete submodular function to a continuous multilinear function F_{ME}:[0,1]^{\mathcal{N}}\to\mathbb{R} , F_{ME}(\mathbf{x})=\mathbb{E}[f(R(\mathbf{x}))]=\sum_{S\subseteq\mathcal{N}}f(S)\prod_{i\in S}x_{i}\prod_{j\notin S}(1-x_{j}), where R(\mathbf{x}) is a random subset of \mathcal{N} in which each element i\in\mathcal{N} is included independently with probability x_{i} . By applying a Frank-Wolfe-like continuous optimization algorithm, a fractional solution is obtained, which is then converted into a discrete solution via a rounding procedure such as Pipage Rounding [ 18 ] and Swap Rounding [ 13 ] . This approach achieves an approximation ratio 1-1/e for monotone functions under matroid constraints. Crucially, the optimization component of this framework generally requires only that the constraint be a down-closed convex polytope. Given that lossless rounding techniques exist for cardinality and matroid constraints, and that knapsack constraints admit nearly lossless rounding via contention resolution schemes [ 14 ] , the multilinear extension framework supports a versatile algorithmic design that is not tied to specific constraint types. Subsequent research has continuously advanced the approximation ratio for non-monotone submodular maximization, from the long-standing 1/e(\approx 0.367) [ 46 ] to (0.372-\varepsilon) [ 22 ] , (0.385-\varepsilon) [ 9 ] , and (0.401-\varepsilon) [ 10 ] . Closing the remaining gap between these results and the theoretical upper bound of 0.478 [ 28 ] remains a significant open challenge in the field. Computing the value of the multilinear extension exactly typically requires exponentially many function evaluations, and random sampling is widely regarded as the only polynomial-query approach for estimating its value. However, such randomness can be undesirable in applications where deterministic outcomes are required, such as safety-critical or reproducibility-sensitive environments. Randomized algorithms provide guarantees in expectation but not necessarily in the worst case, making them less predictable in certain scenarios. Designing deterministic algorithms for submodular maximization, which returns the same solution on every run and guarantees an approximation ratio in the worst case rather than only in expectation, has emerged as an important and active research direction in recent years. Broadly speaking, deterministic algorithms for submodular maximization follow two main paradigms: (i) designing algorithms that are deterministic by construction, and (ii) derandomizing existing randomized algorithms while preserving their approximation guarantees. Under the first paradigm, many classical algorithms for monotone submodular maximization are inherently deterministic. Representative examples include greedy-like algorithms, threshold-based methods, and discrete local search algorithms. The standard greedy algorithm achieves a (1-1/e) -approximation under a cardinality constraint [ 37 ] and a 1/2 -approximation under matroid constraints [ 27 ] , while Sviridenko proposed a (1-1/e) -approximation under a knapsack constraint [ 44 ] . In addition, threshold decreasing algorithms, which iteratively lower a marginal-gain threshold and select elements exceeding the current threshold, provide a deterministic and oracle-efficient alternative to the standard greedy approach, and achieve near-optimal approximation guarantees with significantly improved running time [ 4 ] . Buchbinder et al. [ 5 ] showed that for monotone submodular maximization under a matroid constraint, the split-and-grow algorithm enables deterministic algorithms to surpass the 1/2 barrier, achieving a (1/2+\varepsilon) -approximation. For non-monotone objectives, deterministic local search algorithms were systematically studied by Feige et al. [ 23 ] , establishing constant-factor guarantees for unconstrained submodular maximization. Beyond these general frameworks, several algorithms have been explicitly designed to achieve strong deterministic guarantees. Notably, the twin greedy algorithm proposed by Han et al. [ 29 ] achieves a 1/4 -approximation for non-monotone submodular maximization under matroid constraints, which was later extended to knapsack constraints by Sun et al. [ 43 ] while preserving the same approximation ratio. To the best of our knowledge, this remains the strongest known deterministic guarantee for non-monotone submodular maximization under knapsack constraints. The second paradigm focuses on derandomizing previously randomized algorithms , and has witnessed substantial progress in recent years. Early examples include the random greedy algorithm for cardinality constraints [ 6 ] and the double greedy algorithm for unconstrained non-monotone maximization [ 7 ] , both of which were later systematically derandomized by Buchbinder and Feldman [ 8 ] . More recently, Buchbinder and Feldman [ 11 ] derandomized the non-oblivious local search algorithm, obtaining a deterministic (1-1/e-\varepsilon) -approximation for monotone submodular maximization under matroid constraints. In addition, Chen et al. [ 17 ] derandomized the measured continuous greedy algorithm [ 9 ] , achieving approximation ratios of 0.385-\varepsilon under cardinality constraints and 0.305-\varepsilon under matroid constraints. Very recently, Buchbinder et al. [ 12 ] introduced the Extended Multilinear Extension (EME), a novel derandomization framework that

Read the complete text