A Tight Competitive Ratio for Online Submodular Welfare Maximization.
Amit GanzPranav NutiRoy SchwartzPublished in: CoRR (2023)
Keyphrases
- online algorithms
- competitive ratio
- lower bound
- worst case
- objective function
- upper bound
- online learning
- average case
- greedy algorithm
- single machine
- learning algorithm
- optimal strategy
- convergence rate
- processing times
- approximation algorithms
- branch and bound
- initially unknown
- branch and bound algorithm
- random walk