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

János Balogh, György Dósa, Leah Epstein +1

We prove new lower bounds for suitable competitive ratio measures of two relaxed online packing problems: online removable multiple knapsack, and a recently introduced online minim…