Lower Bounds on the Performance of Online Algorithms for Relaxed Packing Problems.
János BaloghGyörgy DósaLeah EpsteinLukasz JezPublished in: IWOCA (2022)
Keyphrases
- online algorithms
- packing problem
- lower bound
- optimal solution
- upper bound
- online learning
- bin packing
- worst case
- learning algorithm
- competitive ratio
- branch and bound algorithm
- integer programming
- average case
- np hard
- special case
- asymptotically optimal
- objective function
- linear programming
- linear program
- vc dimension
- machine learning