A General Framework for Dynamic Consistent Submodular Maximization

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 cardinalityconstrained 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 1 /2 -O(ε) approximation that is O( 1 /ε 2 ) consistent. For rankk matroid constraints, we construct a 1 /4 -O(ε) approximation to the dynamic optimum that is O( log k /ε 2 ) consistent. * For simplicity, we assume that a deleted element cannot be reinserted in the stream; this assumption is without loss of generality, as we can imagine adding multiple copies of the same element. † A△B = A B ∪ B A denotes the symmetric difference.