A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization.
Niv BuchbinderMoran FeldmanJoseph NaorRoy SchwartzPublished in: FOCS (2012)
Keyphrases
- worst case
- objective function
- greedy algorithm
- approximation algorithms
- lower bound
- error bounds
- submodular functions
- upper bound
- approximation ratio
- np hard
- approximation methods
- closed form
- energy minimization
- min sum
- generalization error bounds
- real time
- handwritten numeral recognition
- special case
- expert systems
- data mining