MathDB

Efficient consistent submodular maximization and the STOC 2025 approximation question

Given a sequence of insertions of elements into a ground set, a monotone submodular function ff accessible through value queries, and a cardinality bound kk, does there exist a randomized algorithm that maintains, after every insertion tt, a set StS_t with ∣St∣≤k|S_t|\le k such that f(St)≥(1−1/e)max⁡{f(T):T⊆At, ∣T∣≤k}f(S_t)\ge (1-1/e)\max\{f(T):T\subseteq A_t,\ |T|\le k\}, while making only O(1)O(1) changes to the maintained set per insertion and using polynomially many value queries overall? Here AtA_t denotes the elements that have arrived by time tt.

References

Primary source

arXiv

Additional references

combinatorial-optimizationsubmodular-optimizationtheoretical-computer-science
Posted · edited

Progress summary

Refreshed
Claimed solved

A September 2026 preprint claims to settle the question, identifying an exact barrier and showing that any improvement requires either exponentially many queries or much more recourse.

The STOC 2025 approximation question concerns efficient submodular maximization that remains consistent as the instance changes. A September 2026 arXiv preprint claims the exact barrier is 2−22-\sqrt{2} and that any fixed improvement requires exponentially many value queries or linear recourse.

Known results

  • Consistent Submodular Maximization (May 2024) claims a deterministic factor-22 impossibility for constant consistency, alongside efficient approximations with weaker consistency.
  • The Cost of Consistency (December 2024) claims randomized information-theoretic ratios of 2/32/3 for general monotone submodular functions and 3/43/4 for coverage functions, plus a polynomial-time randomized 0.510.51 approximation; it leaves the corresponding efficient tradeoff open.
  • A June 2026 framework claims polynomial-time fully dynamic approximations of 1/2−O(ε)1/2-O(\varepsilon) for cardinality constraints and 1/4−O(ε)1/4-O(\varepsilon) for rank-kk matroids with sublinear consistency.

September 2026 sharp-barrier claim

The preprint A Sharp Barrier for Consistent Submodular Maximization claims to close the STOC 2025 question by proving the exact supremum ratio and an exponential-query-or-linear-recourse tradeoff. This claim has not been independently verified in the retrieved material.

Current status (as of September 2026): The 2−22-\sqrt{2} barrier and its query/recourse tradeoff are claimed by a new preprint but remain unverified; earlier partial bounds and the efficient tradeoff question are otherwise established as recorded above.

Sources

Solutions 0

No solutions have been posted yet.