Consistent Submodular Maximization

Paul Duetting, Federico Fusco, Silvio Lattanzi, Ashkan Norouzi-Fard, Morteza Zadimoghaddam
Proceedings of the 41st International Conference on Machine Learning, PMLR 235:11979-11991, 2024.

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 this Paper

BibTeX
@InProceedings{pmlr-v235-duetting24a, title = {Consistent Submodular Maximization}, author = {Duetting, Paul and Fusco, Federico and Lattanzi, Silvio and Norouzi-Fard, Ashkan and Zadimoghaddam, Morteza}, booktitle = {Proceedings of the 41st International Conference on Machine Learning}, pages = {11979--11991}, year = {2024}, editor = {Salakhutdinov, Ruslan and Kolter, Zico and Heller, Katherine and Weller, Adrian and Oliver, Nuria and Scarlett, Jonathan and Berkenkamp, Felix}, volume = {235}, series = {Proceedings of Machine Learning Research}, month = {21--27 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v235/main/assets/duetting24a/duetting24a.pdf}, url = {https://proceedings.mlr.press/v235/duetting24a.html}, 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.} }
Endnote
%0 Conference Paper %T Consistent Submodular Maximization %A Paul Duetting %A Federico Fusco %A Silvio Lattanzi %A Ashkan Norouzi-Fard %A Morteza Zadimoghaddam %B Proceedings of the 41st International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2024 %E Ruslan Salakhutdinov %E Zico Kolter %E Katherine Heller %E Adrian Weller %E Nuria Oliver %E Jonathan Scarlett %E Felix Berkenkamp %F pmlr-v235-duetting24a %I PMLR %P 11979--11991 %U https://proceedings.mlr.press/v235/duetting24a.html %V 235 %X 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.
APA
Duetting, P., Fusco, F., Lattanzi, S., Norouzi-Fard, A. & Zadimoghaddam, M.. (2024). Consistent Submodular Maximization. Proceedings of the 41st International Conference on Machine Learning, in Proceedings of Machine Learning Research 235:11979-11991 Available from https://proceedings.mlr.press/v235/duetting24a.html.

Related Material