A General Framework for Dynamic Consistent Submodular Maximization
2026-06-03 • Data Structures and Algorithms
Data Structures and AlgorithmsMachine Learning
AI summaryⓘ
The authors study how to keep a good solution to a problem that changes over time when items are both added and removed. Unlike previous work that only handled adding items, they create a new method that works even with deletions. Their approach finds solutions that are close to the best possible while only making small changes each time the problem updates. Specifically, they provide algorithms with good accuracy and limited changes under different mathematical constraints called cardinality and matroid constraints.
dynamic submodular maximizationconsistencycardinality constraintmatroid constraintapproximation algorithminsertionsdeletionssublinear consistencyrank-k matroidconstant-factor approximation
Authors
Paul Dütting, Federico Fusco, Silvio Lattanzi, Ashkan Norouzi-Fard, Ola Svensson, Morteza Zadimoghaddam
Abstract
Consistency is an important property in dynamic submodular maximization and entails maintaining a near-optimal solution at all times, making only a small number of adjustments to the solution in each step. Prior work has explored this question for the insertion-only case, where the algorithm faces a stream of $n$ insertions, and has established lower and upper bounds for the cardinality-constrained version of the problem. We consider this question in the fully dynamic setting, where the stream of operations may contain both insertions and deletions. We develop a general framework for designing algorithms for this setting, and instantiate it to obtain the first constant-factor approximations with sublinear consistency. For cardinality constraints, we propose a $\frac 12 - O(\varepsilon)$ approximation that is $O\left(\frac{1}{\varepsilon^2}\right)$ consistent. For rank-$k$ matroid constraints, we construct a $\frac 14 - O(\varepsilon)$ approximation to the dynamic optimum that is $O\left(\frac{\log k}{\varepsilon^2}\right)$ consistent.