Weakly submodular maximization under matroid constraints: performance of standard greedy
For and a matroid of rank , let be monotone and -weakly submodular, meaning that for all disjoint , . Standard forward greedy starts with and repeatedly adds a feasible element of maximum marginal value until no further element can be added. Define its worst-case approximation ratio by , where the infimum ranges over such functions and rank- matroids. The problem is to determine , in particular whether the claimed rank-dependent characterization holds. At , the corresponding classical worst-case guarantee is .
References
- When Weak Submodularity Meets Matroids: How Does Standard Greedy Behave? — arXiv — Qixin Zhang, Shi Fu, Shengminjie Chen, Chao Qian, Dacheng Tao
Source: arXiv
Progress summary
A new preprint claims to determine how badly the usual greedy method can perform under matroid constraints, but the result has not been independently checked.
The problem asks for the worst-case performance of standard greedy when maximizing a monotone weakly submodular function subject to a matroid constraint. Zhang, Fu, Chen, Qian, and Tao claim a sharp rank-dependent characterization, answering the longstanding question beyond cardinality constraints.
Known results
- Uniform matroids admit a constant-factor standard-greedy guarantee (Bian et al., 2014).
- Randomized residual greedy achieves under general matroids (Chen et al., 2018).
- Standard greedy was known to achieve at least , with a rank-dependent bound (Chen et al., 2018).
- A separate 2026 preprint constructs instances with ratio , ruling out a size-independent guarantee.
October 2026 claimed characterization
The new version-1 preprint claims matching bounds giving , implying decay of order for fixed . This is an unverified claim.
Current status (as of October 2026): The claimed sharp characterization would settle the problem, but it remains an unverified version-1 preprint.
Solutions 0
No solutions have been posted yet.