Online bin stretching lower bounds: Improved search of computational proofs

07/11/2022
by   Antoine Lhomme, et al.
0

Online bin stretching is an online problem where some items must be packed in an online fashion in a given number of bins. The items are guaranteed to be able to fit into the bins. However, the online aspect of this problem might force the bins to be "stretched" to a bigger capacity in order to be able to pack all the items. Finding lower and upper bounds on how much the bins need to be stretched in the worst case can be modeled as a 2-player game. Then, computational methods can be used to find lower and upper bounds. We propose here new ideas to speed up such methods to try to obtain better lower bounds. More specifically, we give a way to strongly reduce the computation needed for lower bounds by propagating the game states that can be pruned from the search. With those results, the speed and efficiency of the search for lower bounds has been increased. Moreover, three new lower bounds have been found.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset