The Power of Randomization: Distributed Submodular Maximization on Massive Datasets


Rafael Barbosa, Alina Ene, Huy Nguyen, Justin Ward ;
Proceedings of the 32nd International Conference on Machine Learning, PMLR 37:1236-1244, 2015.


A wide variety of problems in machine learning, including exemplar clustering, document summarization, and sensor placement, can be cast as constrained submodular maximization problems. Unfortunately, the resulting submodular optimization problems are often too large to be solved on a single machine. We consider a distributed, greedy algorithm that combines previous approaches with randomization. The result is an algorithm that is embarrassingly parallel and achieves provable, constant factor, worst-case approximation guarantees. In our experiments, we demonstrate its efficiency in large problems with different kinds of constraints with objective values always close to what is achievable in the centralized setting.

Related Material