An Exponential Speedup in Parallel Running Time for Submodular Maximization without Loss in Approximation.
Eric BalkanskiAviad RubinsteinYaron SingerPublished in: SODA (2019)
Keyphrases
- objective function
- orders of magnitude
- greedy algorithm
- efficient computation
- approximation methods
- parallel processing
- approximation algorithms
- shared memory
- submodular functions
- parallel hardware
- closed form
- data skew
- approximation schemes
- multi core processors
- approximation ratio
- general purpose
- approximation error
- distributed memory
- computer architecture
- search engine
- parallel computing
- parallel implementation