# Metadata

- Title: A General Framework for Dynamic Consistent Submodular Maximization
- Authors: Anonymous
- Year: 2026
- Venue: ICML 2026 submission under review (anonymous reviewer copy)
- Primary group: submodular
- Secondary tags: consistency, fully-dynamic, cardinality, matroid, deletion-robustness, stability, randomized
- Problem: maintain a high-value feasible solution for monotone submodular maximization in a fully dynamic stream with insertions and deletions, while bounding the symmetric-difference change of the solution at every time step
- Main guarantee: gives a `1/2 - O(epsilon)` approximation with `O(1/epsilon^2)` consistency for cardinality constraints, and a `1/4 - O(epsilon)` approximation with `O(log k / epsilon^2)` consistency for rank-`k` matroid constraints
- Key techniques: randomized scheduling of transition windows across robustness levels, separation into robust and non-robust routines, deletion-robust submodular coresets, gradual chunked transitions between old and new solutions, inverse-marginal sampling in the matroid robust routine, threshold-style robust greedy for cardinality
- Status: processed-deep, under-review-anonymous, venue-year-to-verify
- Tags: #submodular #consistency #fully-dynamic #cardinality #matroid #stability #deletion-robustness
- Inbox source: inbox/9658_A_General_Framework_for_D.pdf