# Metadata

- Title: Unconstrained Submodular Maximization in Dynamic Setting
- Authors: Anonymous
- Year: 2026
- Venue: ICML 2026 submission under review (anonymous reviewer copy)
- Primary group: submodular
- Secondary tags: dynamic, unconstrained, non-monotone, incremental, decremental, fully-dynamic, query-complexity
- Problem: maintain a high-value solution for unconstrained non-monotone submodular maximization under dynamic updates, while using sublinear amortized query complexity per update
- Main guarantee: gives a `0.3`-approximation with amortized `O(sqrt(n))` queries in the incremental model, a `0.3`-approximation with amortized `O(sqrt(n))` queries in a decremental model with known deletion order, and a `0.264`-approximation with amortized `O(sqrt(n))` queries in a fully dynamic model where deletion times are revealed at insertion time
- Key techniques: generalized Buchbinder-Feldman-Naor-Schwartz `Extend` subroutine, `sqrt(n)`-sized buffer decomposition, random half-sampling of the permanent block, case split on whether the optimum is concentrated in the permanent block or the buffer, reverse-time decremental analogue, reduction from fully dynamic updates with deletion-time predictions to a maintained decremental instance
- Status: processed-deep, under-review-anonymous, venue-year-to-verify
- Tags: #submodular #dynamic #unconstrained #non-monotone #incremental #decremental #fully-dynamic
- Inbox source: inbox/4836_Unconstrained_Submodular_.pdf