A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization.
Niv BuchbinderMoran FeldmanJoseph NaorRoy SchwartzPublished in: SIAM J. Comput. (2015)
Keyphrases
- worst case
- objective function
- greedy algorithm
- approximation algorithms
- error bounds
- upper bound
- lower bound
- constant factor approximation
- energy minimization
- approximation error
- submodular functions
- expert systems
- closed form
- databases
- approximation ratio
- min sum
- optimal solution
- real world
- efficient computation
- queueing networks
- relative error
- database