On the convergence of computational methods for the online bin stretching problem

Antoine Lhomme, Nicolas Catusse, Nadia Brauner Univ. Grenoble Alpes, CNRS, Grenoble INP, G-SCOP, 38000 Grenoble, France · 2025

Read On the convergence of computational methods for the online bin stretching problem by Antoine Lhomme, Nicolas Catusse, Nadia Brauner Univ. Grenoble Alpes, CNRS, Grenoble INP, G-SCOP, 38000 Grenoble, France (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-17271.txt.

Introduction

Lhomme, Catusse, and Brauner prove that computer searches for a classic packing problem do eventually find the truth, in a paper published in 2025. In online bin stretching, items arrive one by one and must be packed without knowing the future. The best known performance bounds came from computational searches, not proofs. Each search is cut off by time, leaving a nagging doubt: would longer searches keep improving, or stall short of the true optimum?

The authors show the methods converge to the optimal online performance. They also bound how far a stopped search can sit from that optimum. The result gives the search-based bounds a theoretical floor. It extends reassurance to computational approaches for online problems generally. Practitioners can now quote the gap, not just the number.

Catalog record

CREATORAntoine Lhomme, Nicolas Catusse, Nadia Brauner Univ. Grenoble Alpes, CNRS, Grenoble INP, G-SCOP, 38000 Grenoble, France
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE28 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2506-17271

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

On the convergence of computational methods for the online bin stretching problem Antoine Lhomme, Nicolas Catusse, Nadia Brauner Univ. Grenoble Alpes, CNRS, Grenoble INP, G-SCOP, 38000 Grenoble, France Abstract Online bin stretching is an online packing problem where some of the best known lower and upper bounds were found through computational searches. The limiting factor in obtaining better bounds with such methods is the computational time allowed. However, there is still no theoretical guarantee that such methods do converge towards the optimal online performance. This paper shows that such methods do, in fact, converge; moreover, bounds on the gap to the optimal are also given. These results frame a theoretical foundation for the convergence of computational approaches for online problems. 1 Online bin stretching and computational methods The online bin stretching problem, introduced in AZAR200117 , is defined as follows: a finite sequence of items, each characterized by its size (represented by a real number), must be placed into m bins. The items are revealed sequentially; an item, when revealed, must be placed irremediably into a bin before the next one 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 so that, in the end, the load of the fullest bin is minimized. An algorithm that places items into bins has its performance measured through its worst-case input; the performance of an algorithm is called in this problem the stretching factor 1 1 1 If the sequence of items fits exactly into m bins of unit size, then the stretching factor may also be seen as a competitive ratio. . This problem may also be interpreted as an online scheduling problem on m parallel identical machines where the objective is to minimize the makespan (the total time to execute all tasks): using scheduling notations, the problem may be written as P_{m}|online,OPT=1|C_{max} , with OPT=1 indicating that the optimal makespan is known in advance to be of unit duration and with online meaning that items are given in an online fashion. Optimal algorithms (in the sense of stretching factor) for various numbers of available bins are still unknown; some research has been done on both lower and upper bounds for the optimal stretching factor. Interestingly, some of the best known lower and upper bounds (algorithms) for this problem were recently found through computational searches: see Gabay2017 ; BOHM20221 ; lhomme2022online for lower bounds and Liesk for upper bounds – additionally ROB improved the best known algorithm to 1.495 for large m , although without using computational searches. Figure 1 depicts the current state of the art on this problem. Solid squares or solid circles correspond to values that were found through a computational search. Finding optimal online algorithms is still a challenge when the number of bins m is greater than 2. Note that the gap between upper and lower bounds is still important. 2 3 4 5 6 7 8 m\geq 9 1.3 1.33 1.35 1.4 1.45 1.5 Number of bins m Upper bound Lower bound Figure 1 : Best known bounds on the minimal stretching factor of deterministic algorithms for the online bin stretching problem. Solid squares and circles represent bounds that were found with the methods presented in Sections 1.1 and 1.2 . The computational method to find lower bounds may be summarized as follows: the problem is modelled as a two-player zero-sum game, where one player, the adversary , sends items and the other player, the algorithm , places the items into bins. The algorithm aims to minimize the load of the largest bin. By restricting the adversary to a finite set of possible item sizes, the game becomes finite – and hence its min-max value may be computed through a standard min-max algorithm. Since the adversary player is restricted in this game, the min-max value is a lower bound of the best achievable competitive ratio of online deterministic algorithms. By increasing the set of items available to the adversary, one may hope to improve the lower bounds derived from the corresponding game; however, this also greatly expands the game size: the limiting factor of this method in obtaining better bounds becomes computation time. Figure 2 gives an example of an adversarial strategy (from AZAR200117 ) that proves the lower bound \frac{4}{3} when 2 bins are available – such a strategy may be computed through a standard min-max algorithm. (0,0) Next item : 1/3 (0,1/3) Next item : 1/3 (0,2/3) Next item : 2/3 (2/3,2/3) Next item : 2/3 (2/3,{\color[rgb]{0,0,1}4/3}) ({\color[rgb]{0,0,1}4/3},2/3) (0,{\color[rgb]{0,0,1}4/3}) (1/3,1/3) Next item : 1 (1/3,{\color[rgb]{0,0,1}4/3}) ({\color[rgb]{0,0,1}4/3},1/3) (1/3,0) Next item : 1/3 (2/3,0) Next item : 2/3 (2/3,2/3) Next item : 2/3 (2/3,{\color[rgb]{0,0,1}4/3}) ({\color[rgb]{0,0,1}4/3},2/3) ({\color[rgb]{0,0,1}4/3},0) (1/3,1/3) Next item : 1 (1/3,{\color[rgb]{0,0,1}4/3}) ({\color[rgb]{0,0,1}4/3},1/3) Figure 2 : Adversarial strategy showing the lower bound of \frac{4}{3} for the online bin stretching problem where 2 bins are available. In parentheses: occupied volume in each bin. To construct upper bounds, i.e. , algorithms, the same kind of technique has been proposed in Liesk . The problem is once again modelled as a game between the adversary and the algorithm. To ensure that a strategy for the algorithm player in that game corresponds to a true online bin stretching algorithm, the algorithm strategy needs to be able to process any item sequence. Since item sizes may be any real numbers, the method proposed by Liesk is to split possible item sizes into a finite number of intervals, and then to identify item sizes as the corresponding interval: the adversary player does not send an item of some given size but rather an item of size within some interval. In such a game, a strategy for the algorithm player is a valid online bin stretching algorithm. As such, the min-max value of that game yields an upper bound on the optimal performance of an online algorithm. One may then hope that increasing the quantity of intervals results in more precise algorithms and thus better upper bounds. Once again, doing so increases significantly the size of the game tree which makes computation times the limiting factor to obtain better bounds. To summarize, the heart of the computational methods to obtain the lower and upper bounds consists of min-max searches in a game tree. In order to obtain better proofs, one may increase the possibilities of items that may be sent – however, doing so increases exponentially the game tree size. As such, computation times are the limiting factor for obtaining better bounds. A very natural question is then: does increasing item possibilities yield bounds as close as possible to the true optimum value of the online bin stretching problems; in other words, do the lower and upper bound methods for the online bin stretching problem converge, and at what speed? Our paper shows that both methods do indeed converge towards the optimal performance of an online algorithm; moreover, the speed of convergence of these methods will also be discussed. The idea to approximate the competitive ratio of online algorithms was notably developed in CRAS , where the existence of schemes to approximate the optimal competitive ratio for a wide class of scheduling

Read the complete text