A General Framework for Dynamic Consistent Submodular Maximization

arXiv:2606.04946v1 Announce Type: cross 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(arepsilon) approximation that is Oleft(frac{1}{arepsilon^2}right) consistent. For rank-k matroid constraints, we construct a frac 14 - O(arepsilon) approximation to the dynamic optimum that is Oleft(frac{log k}{arepsilon^2}right) consistent.

Source: arXiv cs.LG | 2026-06-04