4 papers · 1 filter
A General Framework for Dynamic Consistent Submodular Maximization
Paul Dütting, Federico Fusco, Silvio Lattanzi +3
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 t…
Clustering with Label Consistency
Diptarka Chakraborty, Hendrik Fichtenberger, Bernhard Haeupler +3
Designing efficient, effective, and consistent metric clustering algorithms is a significant challenge attracting growing attention. Traditional approaches focus on the stability o…
The Cost of Consistency: Submodular Maximization with Constant Recourse
Paul Dütting, Federico Fusco, Silvio Lattanzi +3
In this work, we study online submodular maximization, and how the requirement of maintaining a stable solution impacts the approximation. In particular, we seek bounds on the best…
Consistent Submodular Maximization
Paul Dütting, Federico Fusco, Silvio Lattanzi +2
Maximizing monotone submodular functions under cardinality constraints is a classic optimization task with several applications in data mining and machine learning. In this paper w…