Online Non-monotone DR-Submodular Maximization: 1/4 Approximation Ratio and Sublinear Regret.
Junkai FengRuiqi YangHaibin ZhangZhenning ZhangPublished in: COCOON (2022)
Keyphrases
- approximation ratio
- greedy algorithm
- online learning
- approximation algorithms
- objective function
- np hard
- submodular functions
- special case
- online algorithms
- lower bound
- worst case
- greedy algorithms
- upper bound
- real time
- state space
- online convex optimization
- energy function
- high order
- expert advice
- loss function
- space complexity
- energy minimization
- cost function
- active learning
- search engine
- data sets