{"ID":3049989,"CreatedAt":"2026-06-04T02:13:16.786527022Z","UpdatedAt":"2026-06-06T14:23:19.411228982Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2606.04946","arxiv_id":"2606.04946","title":"A General Framework for Dynamic Consistent Submodular Maximization","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.","short_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$ inser...","url_abs":"https://arxiv.org/abs/2606.04946","url_pdf":"https://arxiv.org/pdf/2606.04946v1","authors":"[\"Paul Dütting\",\"Federico Fusco\",\"Silvio Lattanzi\",\"Ashkan Norouzi-Fard\",\"Ola Svensson\",\"Morteza Zadimoghaddam\"]","published":"2026-06-03T14:35:13Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"cs.LG\",\"stat.ML\"]","methods":"[]","has_code":false}