← All problems

Weakly submodular maximization under matroid constraints: performance of standard greedy

For 0<γ<10<\gamma<1 and a matroid M=(N,I)\mathcal{M}=(N,\mathcal{I}) of rank rr, let f:2N→R≥0f:2^N\to\mathbb{R}_{\ge 0} be monotone and γ\gamma-weakly submodular, meaning that for all disjoint S,T⊆NS,T\subseteq N, ∑e∈T(f(S∪{e})−f(S))≥γ(f(S∪T)−f(S))\sum_{e\in T}\bigl(f(S\cup\{e\})-f(S)\bigr)\ge \gamma\bigl(f(S\cup T)-f(S)\bigr). Standard forward greedy starts with S0=∅S_0=\varnothing and repeatedly adds a feasible element of maximum marginal value until no further element can be added. Define its worst-case approximation ratio by Rgr(γ,r)=inf⁡f(Sgr)/max⁡{f(S):S∈I}R_{\mathrm{gr}}(\gamma,r)=\inf f(S_{\mathrm{gr}})/\max\{f(S):S\in\mathcal{I}\}, where the infimum ranges over such functions and rank-rr matroids. The problem is to determine Rgr(γ,r)R_{\mathrm{gr}}(\gamma,r), in particular whether the claimed rank-dependent characterization Rgr(γ,r)=Θ ⁣(max⁡{γr,γ21+γ(1−γ)r})R_{\mathrm{gr}}(\gamma,r)=\Theta\!\left(\max\left\{\frac{\gamma}{r},\frac{\gamma^2}{1+\sqrt{\gamma(1-\gamma)r}}\right\}\right) holds. At γ=1\gamma=1, the corresponding classical worst-case guarantee is 1/21/2.

References

Source: arXiv

Progress summary

Refreshed
Open · solution reported

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 (1+1/γ)−2(1+1/\gamma)^{-2} under general matroids (Chen et al., 2018).
  • Standard greedy was known to achieve at least 0.4γ2/(γr+1)0.4\gamma^2/(\sqrt{\gamma r}+1), with a rank-dependent bound (Chen et al., 2018).
  • A separate 2026 preprint constructs instances with ratio O(γ/((1−γ)2log⁡n))O(\gamma/((1-\gamma)^2\log n)), ruling out a size-independent guarantee.

October 2026 claimed characterization

The new version-1 preprint claims matching bounds giving Rgr(γ,r)=Θ ⁣(max⁡{γ/r,γ2/(1+γ(1−γ)r)})R_{\mathrm{gr}}(\gamma,r)=\Theta\!\left(\max\left\{\gamma/r,\gamma^2/(1+\sqrt{\gamma(1-\gamma)r})\right\}\right), implying decay of order r−1/2r^{-1/2} for fixed γ\gamma. 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.

Sources

Solutions 0

No solutions have been posted yet.