Consistent Submodular Maximization
<|reference_start|>Consistent Submodular Maximization: Maximizing monotone submodular functions under cardinality constraints is a classic optimization task with several applications in data mining and machine learning. In this paper we study this problem in a dynamic environment with consistency constraints: elements arrive in a streaming fashion and the goal is maintaining a constant approximation to the optimal solution while having a stable solution (i.e., the number of changes between two consecutive solutions is bounded). We provide algorithms in this setting with different trade-offs between consistency and approximation quality. We also complement our theoretical results with an experimental analysis showing the effectiveness of our algorithms in real-world instances.<|reference_end|>
@article{dütting2024consistent,
    title={Consistent Submodular Maximization},
    author={Paul D"utting, Federico Fusco, Silvio Lattanzi, Ashkan Norouzi-Fard,
  Morteza Zadimoghaddam},
    journal={arXiv preprint arXiv:2405.19977},
    year={2024},
    archivePrefix={arXiv},
    eprint={2405.19977},
    primaryClass={cs.DS cs.LG stat.ML}
}