arXiv (Cornell University) · 2015 · 44 citations · 9 references
Open access
ComputingComputer ScienceMachine LearningParallel AlgorithmsParallel ComputingApproximation AlgorithmsData ParallelismDistributed AlgorithmsDistributed ComputingLarge-scale OptimizationOptimization For Machine LearningApproximation GuaranteesDistributed Approximation AlgorithmsDistributed Machine LearningDistributed OptimizationDocument SummarizationSensor PlacementSubmodular MaximizationSubmodular Optimization
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 develop a simple distributed algorithm that is embarrassingly parallel and it 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.
9
Sanjay Ghemawat · Communications of the ACM · 2008 · 18.5K citations · Full text
Finding groups in data: an introduction to cluster analysis
Choice Reviews Online · 1991 · 10.6K citations