Lower bounds on the performance of online algorithms for relaxed packing problems.

János Balogh György Dósa Leah Epstein Lukasz Jez

Published in: CoRR (2022)

Keyphrases

online algorithms
packing problem
lower bound
optimal solution
upper bound
online learning
bin packing
integer programming
np hard
worst case
competitive ratio
learning algorithm
branch and bound algorithm
average case
objective function
sample complexity
decision boundary
support vector machine