CS Paper Radar

An Analytic 0.48-Approximation for Non-Monotone k-Submodular Maximization under a Matroid Constraint

Zizong Wang, Yibo Wang, Wenguo Yang

cs.DS math.OC ·submitted 2026-10-14 12:58 UTC · v2
theory

Abstract

We give a randomized polynomial-time $0.48$-approximation for maximizing a nonnegative non-monotone $k$-submodular function under a matroid constraint, for every $k\ge2$. The algorithm combines a top-two label rule with a nested-chain potential and maximum-weight matroid bases. Its analysis reduces the approximation guarantee to a one-dimensional time allocation: a uniform local lower bound leads to a linear differential equation, concavity closes the remaining interval, and two elementary budgets complete the proof. A strict saving in the time budget absorbs sampling and discretization errors, yielding the exact $0.48$ guarantee in the value-oracle model.

Comment
22 pages, 1 figure, 1 table; author list updated to include Wenguo Yang

Closest papers

Nearest neighbours by meaning across the whole index.

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

cs.DS math.OC ·2026-10-12 ·Shengminjie Chen, Kaifeng Lin, Xiaoming Sun, Jialin Zhang
similarity 0.82
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-\varepsilon)$ \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.

0.14

Stronger Hardness for Submodular Maximization Subject to a Matroid Constraint

cs.DS ·2026-10-05 ·Moran Feldman, Alan Kuhnle
similarity 0.78
Abstract · 13 pages. This version adds a remark about the relationship between this work and the results of arXiv:2610.00545

Maximizing a submodular function subject to a matroid constraint is a cornerstone problem in combinatorial optimization. The state-of-the-art algorithm for this problem obtains $0.401$-approximation~\cite{buchbinder2024constrained}, and the state-of-the-art hardness result shows that no polynomial time algorithm can obtain better than $0.478$-approximation for this problem~\cite{oveisgharan2011submodular}. In this work, we present the first improvement in $15$ years for the hardness result, showing that no polynomial time algorithm in the value-oracle model can obtain better than $8/17 \approx 0.471$-approximation, even for the special case of a cardinality or (simplified) partition matroid constraint.

0.40

On Maximizing a Weakly Submodular Function over a Matroid Constraint via the Greedy Algorithm

cs.DS ·2026-09-04 ·Justin Ward, Moran Feldman
similarity 0.74
Abstract

We consider the problem of approximately maximizing a weakly submodular function using the standard greedy algorithm, which is known to give tight approximation results for such functions under a cardinality constraint. We show that this is not the case for general matroid constraints. For any $γ< 1$, we give a family of $γ$-weakly submodular functions and a simple partition matroid constraint and show that the standard greedy algorithm provides no constant approximation for the resulting constrained maximization problem.

0.41

Nearly-Linear Query Algorithm for Submodular Maximization subject to a Matroid Constraint

cs.DS ·2026-11-03 ·Tatsuya Terao
similarity 0.72
Abstract · 21 pages

We consider monotone submodular maximization subject to a matroid constraint. The seminal continuous greedy algorithm of Calinescu, Chekuri, Pál, and Vondrák~[SICOMP'11] achieves the tight approximation of $(1-1/e)$. Since then, a line of works by Badanidiyuru and Vondrák~[SODA'14], Buchbinder, Feldman, and Schwartz~[SODA'15 \& MOR'17], Kobayashi and Terao~[ICALP'24], Buchbinder and Feldman~[FOCS'24 \& SICOMP'25], and Buchbinder and Feldman~[STOC'25] has developed efficient $(1-1/e-\varepsilon)$-approximation algorithms for this problem. We present a combinatorial randomized $(1-1/e-\varepsilon)$-approximation algorithm that requires $\tilde{O}_{\varepsilon}(n)$ independence-oracle and value-oracle queries, where $n$ is the number of elements in the matroid. This is the first $(1-1/e-\varepsilon)$-approximation algorithm with both independence-oracle and value-oracle query complexities nearly-linear in $n$ and polynomial in $1/\varepsilon$. To achieve this, we develop a new local search algorithm, which we call \emph{protected local search}, based on the potential function of Buchbinder and Feldman~[FOCS'24 \& SICOMP'25].

0.18

From Linear to Polylogarithmic: Dynamic Submodular Maximization over Matroids

cs.DS ·2026-10-26 ·Kiarash Banihashem, Samira Goudarzi, MohammadTaghi Hajiaghayi, Peyman Jabbarzade, Morteza Monemizadeh
similarity 0.71
Abstract

We study the problem of submodular maximization under a matroid constraint. In this problem, there is a monotone submodular function $f: 2^{N} \rightarrow \mathbb{R}^+$ and a matroid $M(N, I)$, accessible via value and independence oracles and the goal is to find the independent set $S \in I$ maximizing the objective function, i.e., $f(S) = \max_{I \in I} f(I)$. In the fully dynamic setting, the active ground set $N \subseteq N$ evolves through element insertions and deletions. The goal is to maintain a solution $S \subseteq N$ with $S \in I$ and $f(S) = \max_{I \subseteq N,, I \in I} f(I)$ after each update. Two approximation algorithms have been proposed to solve this problem: Dütting et al. developed a $(4+ε)$-approximation algorithm with an expected amortized update time of $O\!\bigl(\frac{k^2}ε \log k \log n \log^3 \frac{k}ε\bigr)$, and Banihashem et al. achieved a similar approximation with a better update time $O\!\bigl(k \log k \log^3 \frac{k}ε\bigr)$. However, these methods both become inefficient when the rank $k$ of the matroid is large (e.g., when $k = n^{o(1)}$). The central open question in this line of work is whether a fully dynamic algorithm with polylogarithmic update time exists. We resolve this question by presenting the first fully dynamic algorithm for submodular maximization over matroids with polylogarithmic update time. Our algorithm maintains a $(4+ε)$-approximate solution with expected amortized update time $poly(\log n, ε^{-1})$, where $n = |N|$. In particular, the update time is independent of the matroid rank $k$, thereby eliminating the dependence on $k$ and settling the open problem.

0.30

Breaking the 1/3 Barrier for constrained $\boldsymbol{k}$-Submodular Maximization: A Proportional Top-2 Randomized Framework

cs.DS ·2026-09-14 ·Siyuan Chen, Shengminjie Chen, Suixiang Gao, Zheyu Jiang, Chenhao Wang +1 more
similarity 0.70
Abstract

$k$-submodularity generalizes submodularity by allowing each selected element to be assigned one of $k$ labels. We study the maximization of a non-monotone $k$-submodular function, where $k\ge2$, under matroid and knapsack constraints. We develop a proportional top-2 randomized framework that achieves an approximation ratio of $\sqrt2-1\approx0.4142$ under either constraint, breaking the previous $1/3$ barrier. Once an element is selected, its label is chosen from the two labels with the largest marginal gains, with probabilities proportional to their positive parts. The analysis separates replacement, pure-addition, and residual-deletion losses, and proves a sharp local loss certificate for this rule. We then give a Bellman analysis using the same local certificate. It gives a $1/2$-approximation under a cardinality constraint and strengthens the knapsack guarantee to $1/2$ without changing the algorithm. The $1/2$ guarantees are oracle-optimal for $k=2$ and asymptotically tight as $k\to\infty$. The value-oracle complexities are $O(Bnk)$ for cardinality, where $B$ is the cardinality bound, $O(n^2k)$ for matroid, and $O(n^3k^2)$ for knapsack.

0.20

A Tight Oracle Threshold for \(k\)-Submodular Maximization

cs.DS ·2026-10-19 ·Siyuan Chen
theory similarity 0.68
Abstract · 5 pages

We prove that, for every \(\varepsilon>0\), a \((\frac{k}{2k-1}+\varepsilon)\)-approximation algorithm for maximizing monotone \(k\)-submodular functions requires exponentially many value-oracle queries. This improves the \(\frac{k+1}{2k}\) oracle bound of Iwata, Tanigawa, and Yoshida. Their \(\frac{k}{2k-1}\)-approximation algorithm therefore gives the exact threshold in the monotone setting. For \(k\ge5\), our bound also matches, up to an arbitrarily small loss, Aggarwal's recent approximation guarantee for non-monotone \(k\)-submodular maximization.

0.10

When Weak Submodularity Meets Matroids: How Does Standard Greedy Behave?

cs.DM math.OCcs.LG ·2026-10-18 ·Qixin Zhang, Shi Fu, Shengminjie Chen, Chao Qian, Dacheng Tao
theory similarity 0.68
Abstract · 33 pages

Weakly submodular maximization finds numerous applications in machine learning, data mining and statistics. In particular, under a cardinality constraint, the standard greedy algorithm is known to attain the tight $(1-e^{-γ})$-approximation guarantee, where $γ$ denotes the submodularity ratio. However, when considering general matroid constraints, \emph{how well standard greedy can perform} has remained a longstanding open question. In this paper, we resolve this question by studying the worst-case approximation guarantee $R_{\mathrm{gr}}(γ,r)$ of standard forward greedy, where $r$ is the rank of matroid. Specifically, our first contribution is the following refined lower bound \begin{equation*} R_{gr}(γ,r)\ge \max\left\{ \fracγ{r}, \frac{γ^2} {B_γ+\sqrt{γ(r-1)}}, \frac{γ^{r+1}} {2-γ+γ^{r+1}}, \frac{γ^2} {14\left(B_γ+\sqrt{γ(1-γ)(r-1)}\right)} \right\}, \end{equation*} where $B_γ\triangleq2-γ+γ^2$. This lower bound not only strictly improves upon the previous guarantee of $0.4γ^2/(1+\sqrt{γr})$, but also can recover the classical $1/2$-approximation guarantee at $γ=1$. Subsequently, a corresponding upper bound is established for $R_{\mathrm{gr}}(γ,r)$, namely, \begin{equation}\label{eq_upper_abstract} R_{gr}(γ,r) \le\min\left\{\frac{1}{2},20\max\left\{\fracγ{r}, \frac{γ^2}{B_γ+ \sqrt{γ(1-γ)(r-1)}}\right\}\right\}. \end{equation} For every fixed $γ\in(0,1)$, this equation effectively sharpens the recent $O_γ(1/\log(n-1))$ upper bound to $O_γ(r^{-1/2})$, where $n$ is the size of ground set. Putting all these results together, we eventually can obtain \[R_{gr}(γ,r) = Θ\left( \max\left\{\fracγ{r}, \frac{γ^2} {1+\sqrt{γ(1-γ)r}}\right\} \right).\]

0.09