# Metadata

- Title: Consistent Submodular Maximization
- Authors: Paul Dutting, Federico Fusco, Silvio Lattanzi, Ashkan Norouzi-Fard, Morteza Zadimoghaddam
- Year: 2024
- Venue: ICML 2024
- Primary group: submodular
- Secondary tags: consistency, dynamic-insertion, cardinality, streaming, local-search, stability
- Problem: monotone submodular maximization under a cardinality constraint in an insertion-only stream, with explicit control of how much the maintained solution may change after each insertion
- Main guarantee: proves that no deterministic constant-consistency algorithm can beat a `2 - epsilon` approximation, gives a `1`-consistent `3.147 + O(1/k)`-approximation algorithm, and gives an `O~(1/epsilon)`-consistent `(phi + 1 + 9 epsilon)`-approximation algorithm where `phi` is the golden ratio
- Key techniques: benchmark set with exponential admission threshold, value decay bound for dropped benchmark elements, min-swap via low marginal elements, chasing local optima with bounded extra swaps, split proof depending on whether a recent local optimum exists
- Status: processed-deep
- Tags: #submodular #consistency #streaming #cardinality #stability #local-search
- Inbox source: inbox/duetting24a.pdf