Computational bounds on randomized algorithms for online bin stretching

Antoine Lhomme, Nicolas Catusse, Nadia Brauner

A frequently studied performance measure in online optimization is competitive analysis. It corresponds to the worst-case ratio, over all possible inputs of an algorithm, between t…