An Exponential Speedup in Parallel Running Time for Submodular Maximization without Loss in Approximation.
Eric BalkanskiAviad RubinsteinYaron SingerPublished in: CoRR (2018)
Keyphrases
- objective function
- orders of magnitude
- submodular functions
- parallel processing
- greedy algorithm
- lower bound
- closed form
- efficient computation
- parallel implementation
- approximation algorithms
- approximation error
- high order
- database systems
- relative error
- parallel computation
- data skew
- constant factor approximation
- massively parallel
- shared memory
- distributed memory
- energy minimization
- error bounds
- approximation methods
- np hard
- error tolerance
- image segmentation
- case study