A New Framework for Distributed Submodular Maximization

A wide variety of problems in machine learning, including exemplar clustering, document summarization, and sensor placement, can be cast as constrained submodular maximization problems. A lot of recent effort has been devoted to developing distributed algorithms for these problems. However, these results suffer from high number of rounds, suboptimal approximation ratios, or both. We develop a framework for bringing existing algorithms in the sequential setting to the distributed setting, achieving near optimal approximation ratios for many settings in only a constant number of MapReduce rounds. Our techniques also give a fast sequential algorithm for non-monotone maximization subject to a matroid constraint.

Authors

• Rafael da Ponte Barbosa
• Alina Ene
• Huy L. Nguyen 0001
• Justin Ward

Keywords

• Approximation algorithms
• Greedy algorithms
• Distributed algorithms
• Standards
• Computer science
• Clustering algorithms
• Partitioning algorithms
• Submodular Maximization
• Fast Algorithm
• Sequential Algorithm
• Distributed Algorithm
• Approximate Ratio
• Machine Learning Problems
• MapReduce
• Wide Variety Of Problems
• Video Summarization
• Cylindrical
• Parallelization
• Standard Algorithm
• Constant Factor
• Single Element
• System Constraints
• Single Machine
• Parallel Algorithm
• Algorithm Running
• Integral Solution
• Fractional Solution
• Non-monotonic Function
• Communication Rounds
• Distributed submodular maximization