Nearly Optimal Competitive Ratio for Online Allocation Problems with Two-sided Resource Constraints and Finite Requests.
Qixin ZhangWenbing YeZaiyi ChenHaoyuan HuEnhong ChenYu YangPublished in: ICML (2023)
Keyphrases
- competitive ratio
- resource constraints
- online algorithms
- allocation problems
- online learning
- lower bound
- single machine
- average case
- optimal strategy
- resource allocation
- resource availability
- processing times
- initially unknown
- learning algorithm
- worst case
- optimal solution
- routing problem
- upper bound
- scheduling problem
- dynamic programming
- decision boundary
- temporal constraints
- convergence rate
- uniform distribution
- global optimization