Calendrier des animations scientifiques

TBA

TBA

Online bin stretching is an online packing problem where some of the best known lower and upper bounds were found through computational searches.

In this problem a finite sequence of items, each defined by a real number denoting its size, must be placed into m bins. Items are revealed sequentially: whenever an item is revealed, it must be placed irremediably into a bin before the next item is shown. The whole set of items given is also known to fit inside m bins of unit size. The objective is to place all the items into the bins to minimize the load of the fullest bin. This is similar to the online scheduling problem on m machines with known makespan: Pm | Online, Cmax = 1 | Cmax.

We consider computational searches that give verifiable trees which prove lower or upper bounds on the best possible online algorithms. The limiting factor in obtaining better bounds with such methods is the computational time allowed.

We give a theoretical guarantee that such methods do converge towards the optimal online performance. These results frame a theoretical framework for showing the convergence of computational approaches for online problems.

In collaboration with Nicolas Catusse and Nadia Brauner.
Link to Arxiv preprint: https://arxiv.org/abs/2506.17271

TBA