2024/05/30 by Paul Dütting, Dütting, Paul, Federico Fusco +7 · 1 citation
Computer Science · #Advanced Algebra and Logic #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Rough Sets and Fuzzy Logic
paper · pdf · doi:10.48550/arxiv.2405.19977
openalex publication_date 2024/05/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.