Consistent Submodular Maximization
Abstract
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). In this setting, we provide algorithms 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.
Cite
Text
Duetting et al. "Consistent Submodular Maximization." International Conference on Machine Learning, 2024.Markdown
[Duetting et al. "Consistent Submodular Maximization." International Conference on Machine Learning, 2024.](https://mlanthology.org/icml/2024/duetting2024icml-consistent/)BibTeX
@inproceedings{duetting2024icml-consistent,
title = {{Consistent Submodular Maximization}},
author = {Duetting, Paul and Fusco, Federico and Lattanzi, Silvio and Norouzi-Fard, Ashkan and Zadimoghaddam, Morteza},
booktitle = {International Conference on Machine Learning},
year = {2024},
pages = {11979-11991},
volume = {235},
url = {https://mlanthology.org/icml/2024/duetting2024icml-consistent/}
}