A General Framework for Dynamic Consistent Submodular Maximization

Paul Duetting, Federico Fusco, Silvio Lattanzi, Ashkan Norouzi-Fard, Ola Svensson, Morteza Zadimoghaddam
Proceedings of the 43rd International Conference on Machine Learning, PMLR 306:27136-27151, 2026.

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 $\tfrac 12 - O(\varepsilon)$ approximation that is $O\left(\tfrac{1}{\varepsilon^2}\right)$ consistent. For rank-$k$ matroid constraints, we construct a $\tfrac 14 - O(\varepsilon)$ approximation to the dynamic optimum that is $O\left(\tfrac{\log k}{\varepsilon^2}\right)$ consistent.

Cite this Paper

BibTeX
@InProceedings{pmlr-v306-duetting26a, title = {A General Framework for Dynamic Consistent Submodular Maximization}, author = {Duetting, Paul and Fusco, Federico and Lattanzi, Silvio and Norouzi-Fard, Ashkan and Svensson, Ola and Zadimoghaddam, Morteza}, booktitle = {Proceedings of the 43rd International Conference on Machine Learning}, pages = {27136--27151}, year = {2026}, editor = {Zhang, Tong and Dudik, Miroslav and Jaggi, Martin and Agarwal, Alekh and Li, Sharon and Schuurmans, Dale and Zhu, Jerry and Berkenkamp, Felix and Dong, Hanze and Bietti, Alberto}, volume = {306}, series = {Proceedings of Machine Learning Research}, month = {06--11 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v306/main/assets/duetting26a/duetting26a.pdf}, url = {https://proceedings.mlr.press/v306/duetting26a.html}, 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 $\tfrac 12 - O(\varepsilon)$ approximation that is $O\left(\tfrac{1}{\varepsilon^2}\right)$ consistent. For rank-$k$ matroid constraints, we construct a $\tfrac 14 - O(\varepsilon)$ approximation to the dynamic optimum that is $O\left(\tfrac{\log k}{\varepsilon^2}\right)$ consistent.} }
Endnote
%0 Conference Paper %T A General Framework for Dynamic Consistent Submodular Maximization %A Paul Duetting %A Federico Fusco %A Silvio Lattanzi %A Ashkan Norouzi-Fard %A Ola Svensson %A Morteza Zadimoghaddam %B Proceedings of the 43rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2026 %E Tong Zhang %E Miroslav Dudik %E Martin Jaggi %E Alekh Agarwal %E Sharon Li %E Dale Schuurmans %E Jerry Zhu %E Felix Berkenkamp %E Hanze Dong %E Alberto Bietti %F pmlr-v306-duetting26a %I PMLR %P 27136--27151 %U https://proceedings.mlr.press/v306/duetting26a.html %V 306 %X 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 $\tfrac 12 - O(\varepsilon)$ approximation that is $O\left(\tfrac{1}{\varepsilon^2}\right)$ consistent. For rank-$k$ matroid constraints, we construct a $\tfrac 14 - O(\varepsilon)$ approximation to the dynamic optimum that is $O\left(\tfrac{\log k}{\varepsilon^2}\right)$ consistent.
APA
Duetting, P., Fusco, F., Lattanzi, S., Norouzi-Fard, A., Svensson, O. & Zadimoghaddam, M.. (2026). A General Framework for Dynamic Consistent Submodular Maximization. Proceedings of the 43rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 306:27136-27151 Available from https://proceedings.mlr.press/v306/duetting26a.html.

Related Material