  Computing lower and upper bounds on the competitive ratio of online
algorithms is a challenging question: For a minimization combinatorial problem,
proving a competitive ratio for a given algorithm leads to an upper bound.
However computing lower bounds requires a proof on all algorithms. This can be
modeled as a 2-player game where a strategy for one of the players is a proof
for the lower bound. The tree representing the proof can can be found
computationally. This method has been used with success on the online bin
stretching problem where a set of items must be packed online in $m$ bins. The
items are guaranteed to fit into the $m$ bins. However, the online procedure
might require to stretch the bins to a larger capacity in order to be able to
pack all the items. This stretching factor is the objective to be minimized. We
propose original ideas to strongly improve the speed of computer searches for
lower bound: propagate the game states that can be pruned from the search and
improve the speed and memory usage in the dynamic program which is used in the
search. These improvements allowed to increase significantly the speed of the
search and hence to prove new lower bounds for the bin stretching problem for
6, 7 and 8 bins.
