The power of randomization : distributed submodular maximization on massive datasets
- Submitting institution
-
The University of Warwick
- Unit of assessment
- 11 - Computer Science and Informatics
- Output identifier
- 5968
- Type
- E - Conference contribution
- DOI
-
-
- Title of conference / published proceedings
- 32nd International Conference on Machine Learning
- First page
- 1236
- Volume
- 37
- Issue
- -
- ISSN
- -
- Open access status
- -
- Month of publication
- July
- Year of publication
- 2015
- URL
-
-
- Supplementary information
-
-
- Request cross-referral to
- -
- Output has been delayed by COVID-19
- No
- COVID-19 affected output statement
- -
- Forensic science
- No
- Criminology
- No
- Interdisciplinary
- No
- Number of additional authors
-
3
- Research group(s)
-
T - Theory and Foundations
- Citation count
- -
- Proposed double-weighted
- No
- Reserve for an output with double weighting
- No
- Additional information
- Published in a premier conference in machine learning, this paper gives the first massively parallel algorithm for submodular maximization (a fundamental primitive with many applications) that has strong provable performance guarantees. It introduces the technique of randomly partitioning the input before distributing it among the machines. This technique, which was also independently discovered by Mirrokni and Zadimoghaddam (Google), has been widely used in subsequent works: for example, for maximum matching and minimum vertex cover (Google, Columbia University, University of Pennsylvania, TU Berlin), column subset selection (Princeton, Google, Utah), and data summarization (Yale, Google).
- Author contribution statement
- -
- Non-English
- No
- English abstract
- -