#  Online bin stretching lower bounds: Improved search of computational proofs

Antoine Lhomme, Olivier Romane, Nicolas Catusse, Nadia Brauner

###### Contents

  1. 1 Online bin stretching
  2. 2 Finding lower bounds
  3. 3 Algorithm-winning packings pruning method
  4. 4 Knowing which item can be sent next
  5. 5 Results
  6. 6 Conclusion and perspectives
  7. 7 Appendix
    1. 7.1 Proof of Property 3.5
    2. 7.2 Proof of Property 3.6

## Abstract

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.

## Introduction

In online bin stretching, introduced by Azar and Regev (2001), we are given
$m$ bins and we have to pack a set of objects in the bins while the items
arrive one by one (hence the name online). Any item revealed must be packed
irrevocably before the next one is revealed. Bins do not have a capacity
constraint, in the sense that any item can always be packed in any bin no
matter which items are already in the bin. The set of items sent must also
satisfy the following constraint: they must fit into $m$ bins of unit size.
The goal is to pack items in the bins in order to minimize the load of the
largest bin.

The following application of the bin stretching problem is from Azar and Regev
(2001). Some files are stored in $m$ servers, each of unit capacity, and are
sent one by one in some order to $m$ other servers. The only information known
is that the files were initially stored in $m$ servers of unit capacity. Then,
the question is: how large do the new servers need to be to store the files?
How can we design an algorithm to place the files in the new servers?

To clarify the online bin stretching problem, we give in Figure 1 a simple
example with 2 bins ($m=2$). First, an item of size $1/2$ is given and placed
in the first bin. Then, an item of size $1/2$ is given and placed in the
second bin. But now, an item of size $1$ is given. The first bin needs to be
stretched to a capacity of $3/2$ in order to contain this new item - hence the
name bin stretching. This set of items does not violate the constraints, since
they could fit into $2$ bins of size 1: the two items of size $1/2$ could have
been placed together.

$1$$1/2$ (a) First item: $1/2$

$1$$1/2$$1/2$ (b) Second item: $1/2$

$1$$3/2$$1/2$$1/2$$1$ (c) Third item: $1$

Figure 1: Online bin stretching example

In the previous example, we saw that we may need to stretch bins in order to
fit all of the items. What is the smallest size to which the bins must be
stretched in order to pack any set of items? And how to pack the items into
bins?

An approach given by Gabay et al. (2017) is to model this problem as a two-
player game. One player, the adversary, gives items which must be packed into
bins by the other player, the algorithm. The algorithm aims to stretch the
bins as little as possible, while the adversary tries to give items to force
the algorithm to stretch the bins as much as possible. Using this model, it is
possible to find lower bounds on the performance of online bin stretching
algorithms using computer searches. Using this method, several bounds have
been found. However, the speed of such methods is the main limiting factor
when aiming to obtain better bounds.

We restate the idea from Gabay et al. (2017) in Section 2, then we propose new
ideas to improve the speed of computer searches for lower bounds in Section 3
and Section 4. With the new ideas proposed, three new lower bounds have been
found, and the search for lower bounds is faster (Section 5).

##  1 Online bin stretching

In all the following, the number of bins $m$ is fixed. To give a formalisation
of the online bin stretching problem, let us first define possible sets of
items that can be sent as instances. Since the items that are sent can fit
into $m$ bins of unit size, we give the following definitions:

######  Definition 1.1 (Bin stretching instance).

A bin-stretching instance is a finite sequence of strictly positive numbers
$(x_{1},\dots,x_{k})$ such that:
There exists a partition $P_{1},\dots,P_{m}$ of the integers $\\{1,\dots,k\\}$
such that

$\forall i\in\\{1,\dots,m\\}\;\;\;\;\sum_{j\in P_{i}}x_{j}\leq 1$

We write $\mathcal{I}_{BS}$ the set of bin-stretching instances.

An empty instance $I$ is noted $\emptyset$.

######  Definition 1.2 (Extension of bin-stretching instances).

A real positive number $y$ is called an extension of a bin-stretching instance
$I=(x_{1},\dots,x_{k})$ if the sequence $(x_{1},\dots,x_{k},y)$ is a bin-
stretching instance. We note the instance $(x_{1},\dots,x_{k},y)$ as $I\oplus
y$. In a similar manner, a finite sequence of real positive numbers
$(y_{1},\dots,y_{j})$ is an extension of $I$ if the sequence
$(x_{1},\dots,x_{k},y_{1},\dots,y_{j})$ is a bin-stretching instance.

After sending the items of an instance (which can be empty), only items that
are extensions of the instance can be sent next. Here is a simple yet useful
property on extensions:

######  Property 1.1.

Let $I\in\mathcal{I}_{BS}$ be an instance, and $y$ be an extension of $I$.
Then any $y^{\prime}<y$ is also an extension of $I$.

###### Proof.

Since the items of the instance and the item of size $y$ can fit into $m$ bins
of size 1, then the items of the instance and any item of size $y^{\prime}<y$
can also fit into $m$ bins of size 1. ∎

We define an online bin stretching algorithm follows: an online bin stretching
algorithm receives a set of objects $I$, an arrangement $P$ of these objects
in the bins and a new object $y$ to be placed; it returns the index of the bin
in which the algorithm places this new object. We write $\mathcal{A}_{BS}$ the
set of all bin-stretching algorithms.

######  Definition 1.3 (Online bin stretching algorithm).

An online bin stretching algorithm associates to a triplet $(I,y,P)$, where
$I=(x_{1},\dots,x_{k})$ being a bin-stretching instance, $y$ an extension of
$I$, and $P=(P_{1},\dots,P_{m})$ a partition of the integers
$\\{1,\dots,k\\}$, an integer between $1$ and $m$ (included).

######  Definition 1.4 (Result of an algorithm on an instance).

Let $A$ be a bin-stretching algorithm and $I=(x_{1},\dots,x_{k})$ be an
instance of bin-stretching. We iteratively construct the partitions
$P^{0},\dots,P^{k}$ as follows:

  * •

$\forall i\in\\{1,\dots,m\\}\;\;\;\;P_{i}^{0}=\emptyset$

  * •

$\forall i\in\\{1,\dots,m\\},\forall
j\in\\{1,\dots,k\\}\;\;\;\;P_{i}^{j}=\begin{cases}P_{i}^{j-1}\cup\\{j\\}&\text{if
}A((x_{1},\dots,x_{j-1}),x_{j},P^{j-1})=i\\\
P_{i}^{j-1}&\text{otherwise}\end{cases}$

The partition $P^{j}$ corresponds to the arrangement of the first $j$ objects
of the instance $I$ according to the algorithm $A$. We can then define the
result of the algorithm $A$ on the instance $I$, noted $R(I,A)$:

$R(I,A)=\max_{i\in\\{1,\dots,m\\}}\sum_{j\in P_{i}}x_{j}$

The result of an instance on an algorithm corresponds to the load of the
fullest bin after the algorithm places all the objects of the instance.

To analyze the performance of algorithms, we look at their worst-case:

######  Definition 1.5 (Stretching-factor of a bin-stretching algorithm).

For a bin-stretching algorithm $A$, we define its stretching-factor
$s_{BS}(A)$:

$s_{BS}(A)=\max_{I\in\mathcal{I}_{BS}}R(I,A)$

We want to find the best stretching-factor that is achievable by an algorithm,
defined as follows:

######  Definition 1.6 (Optimal stretching-factor)).

$s^{*}=\min_{A\in\mathcal{A}_{BS}}s_{BS}(A)=\min_{A\in\mathcal{A}_{BS}}\;\;\max_{I\in\mathcal{I}_{BS}}R(I,A)$

This lower bound tells us that any online bin stretching algorithm needs, in
the worst case, to stretch the bins to a factor of at least $s^{*}$ to place
all the items.

Computing $s^{*}$ is a difficult task, so we instead aim to find both lower
and upper bounds on $s^{*}$, and we try to reduce the gap between the two as
much as possible. To obtain a lower bound on $s^{*}$, we can propose a tree
proof that modelizes all possible algorithms on a few well chosen instances.

######  Definition 1.7 (Tree proof).

  1. 1.

The tree has a finite number of nodes.

  2. 2.

Each node $\mathcal{T}=(I,P,y)$ that is not a leaf corresponds to a bin-
stretching instance $I$, a partition $P$ of the objects in the bins and an
extension $y$ of $I$.

  3. 3.

The root is of the form
$\mathcal{R}=(\emptyset,(\emptyset,\dots,\emptyset),y)$.

  4. 4.

Each leaf $\mathcal{L}=(I,P)$ corresponds to a bin-stretching instance $I$ and
a packing $P$ of the objects in the bins.

  5. 5.

The children of a node $\mathcal{T}=(I,P,y)$, with $|I|=k$, are defined as all
the possibilities to place the new item $y$ in a bin, so a node has at most
$m$ children. In a more formal manner, for each bin $i$, there exists a child
of $\mathcal{T}$ which is of the form $\mathcal{T}_{i}=(I\oplus
y,P^{\prime},y^{\prime})$ or of the form $\mathcal{L}_{i}=(I\oplus
y,P^{\prime})$, with $P_{i}^{\prime}=P_{i}\cup\\{k+1\\}$ and for any $j\neq
i$, $P_{j}^{\prime}=P_{j}$.

  6. 6.

We define the value of a leaf as the value of the fullest bin, and we define
the value of the tree as the minimum over the values of the leaves.

Finding a tree of a certain value is a lower bound of $s^{*}$ (see proof
below). Figure 2 is an example of such a tree, proving that for $m=2$ bins,
$s^{*}\geq\frac{4}{3}$. For readability, we only write on each node the loads
of the bins and the next item that is sent.

$(0,0)$
$1/3$$(1/3,0)$
$1/3$$(1/3,1/3)$
$1$$({\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\pgfsys@color@rgb@stroke{0}{0}{1}\pgfsys@invoke{}\pgfsys@color@rgb@fill{0}{0}{1}\pgfsys@invoke{}4/3},1/3)$$(1/3,{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\pgfsys@color@rgb@stroke{0}{0}{1}\pgfsys@invoke{}\pgfsys@color@rgb@fill{0}{0}{1}\pgfsys@invoke{}4/3})$$(2/3,0)$
$2/3$$({\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\pgfsys@color@rgb@stroke{0}{0}{1}\pgfsys@invoke{}\pgfsys@color@rgb@fill{0}{0}{1}\pgfsys@invoke{}4/3},0)$$(2/3,2/3)$
$2/3$$({\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\pgfsys@color@rgb@stroke{0}{0}{1}\pgfsys@invoke{}\pgfsys@color@rgb@fill{0}{0}{1}\pgfsys@invoke{}4/3},2/3)$$(2/3,{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\pgfsys@color@rgb@stroke{0}{0}{1}\pgfsys@invoke{}\pgfsys@color@rgb@fill{0}{0}{1}\pgfsys@invoke{}4/3})$$(0,1/3)$
$1/3$$(1/3,1/3)$
$1$$({\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\pgfsys@color@rgb@stroke{0}{0}{1}\pgfsys@invoke{}\pgfsys@color@rgb@fill{0}{0}{1}\pgfsys@invoke{}4/3},1/3)$$(1/3,{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\pgfsys@color@rgb@stroke{0}{0}{1}\pgfsys@invoke{}\pgfsys@color@rgb@fill{0}{0}{1}\pgfsys@invoke{}4/3})$$(0,2/3)$
$2/3$$(0,{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\pgfsys@color@rgb@stroke{0}{0}{1}\pgfsys@invoke{}\pgfsys@color@rgb@fill{0}{0}{1}\pgfsys@invoke{}4/3})$$(2/3,2/3)$
$2/3$$({\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\pgfsys@color@rgb@stroke{0}{0}{1}\pgfsys@invoke{}\pgfsys@color@rgb@fill{0}{0}{1}\pgfsys@invoke{}4/3},2/3)$$(2/3,{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\pgfsys@color@rgb@stroke{0}{0}{1}\pgfsys@invoke{}\pgfsys@color@rgb@fill{0}{0}{1}\pgfsys@invoke{}4/3})$

Figure 2: Tree proof of the lower bound 4/3 for 2 bins

######  Property 1.2.

The value of any tree proof is a lower bound of $s^{*}$.

###### Proof.

Let $\mathcal{T}$ be a tree proof of value $v$ and of root $\mathcal{R}$. We
will show that $s^{*}\geq v$.
Let $A\in\mathcal{A}_{BS}$ be an algorithm. We construct an instance $I$ such
that the result of the algorithm on the instance $R(I,A)$ is at least $v$. To
do so, we follow nodes $\mathcal{T}_{i}=(I_{i},P_{i},y_{i})$ in the tree as
follows:

  * •

$I_{0}=\emptyset$

  * •

$\mathcal{T}_{0}=\mathcal{R}$

  * •

If $\mathcal{T}_{i}=(I_{i},P_{i},y_{i})$ is not a leaf, the algorithm decides
to place the item $y_{i}$ in the bin $A(I_{i},P_{i},y)$. We then define
$\mathcal{T}_{i+1}$ to be the child node of $\mathcal{T}_{i}$ corresponding to
placing the item $y_{i}$ in the bin $A(I_{i},P_{i},y_{i})$, which always
exists by definition of a tree proof.

  * •

If $\mathcal{T}_{i}$ is a leaf, then by construction of the tree, the value of
the leaf corresponds exactly to the result of the instance $I_{i}$ on the
algorithm $A$.

Eventually, since the tree is finite, a leaf $\mathcal{L}=(I,P)$ is reached,
and its value corresponds exactly to the result of the instance $I$ on the
algorithm $A$. Since the value of the tree $\mathcal{T}$ is defined as the
smallest value of a leaf, we have,

$v(\mathcal{T})\leq R(I,A)\leq s_{BS}(A)$

So,

$\forall A\in\mathcal{A}_{BS},v(\mathcal{T})\leq s_{BS}(A)$

Hence $v(\mathcal{T})\leq s^{*}$. ∎

##  2 Finding lower bounds

We aim to find lower bounds of $s^{*}$ through computer searches. To do so, we
use similar methods as first introduced by Gabay et al. (2017) and improved by
Böhm and Simon (2020). We will first restate the method and then propose
improvements.

Computing the exact value of $s^{*}$ is a difficult task. The stretching
factor of any algorithm is an upper-bound of $s^{*}$. To obtain a lower bound,
we can model the problem as a 2-player game, one being the algorithm trying to
fit items in the bins, and one being the adversary proposing items. Then we
can explore informatically a game tree corresponding to this problem.

In order to deal with integer values and to have a finite game, we scale all
the previous definitions by a certain factor $g$, such that all the bins have
capacity $g\in\mathbb{N}^{*}$, and we restrict the item weights to
$\\{1,\dots,g\\}$. Eventually, we increase the value of $g$ so that more items
can be proposed, and better bounds can be found.

The goal of the player "adversary" is to propose items such that no matter
what the algorithm does, one bin will reach at least a certain value $t$, with
$t>g$. If we succeed in finding such a strategy for the player "adversary",
then a tree proof of value $t/g$ has been constructed, and we have obtained a
lower bound of $s^{*}$:

$s^{*}\geq\frac{t}{g}$

This means that any online bin-stretching algorithm has a stretching-factor of
at least $\frac{t}{g}$ (as in Figure 2).

The adversary can only send items such that the items fit into $m$ bins of
size $g$. If the adversary cannot send any more items, and no bin is filled
with items of total size greater or equal to $t$, then the algorithm wins. If
a bin is filled with items of total size greater or equal to $t$ then the
adversary wins.

We can then find a lower bounds of $t/g$ on $s^{*}$ by computing a tree proof
value $t/g$.

So far, the following lower bounds have been found:

  * •

Azar and Regev (2001) have established the general lower bound of 4/3 for any
number of bins.

  * •

Gabay et al. (2017) have found the lower bounds 19/14 for 3 and 4 bins through
computer searches of tree proofs.

  * •

Böhm and Simon (2020) proved the lower bound of 19/14 for 5, 6, 7 and 8 bins
and improved the lower bound of 19/14 for 3 bins to 112/82 with the same
method.

Upper bounds seem more tricky to find, as one needs to construct an algorithm
and then analyze the algorithm worst case. So far, the following upper bounds
have been found:

  * •

Kellerer et al. (1997) found an upper bound of 4/3 for 2 bins - hence the
algorithm is optimal.

  * •

Azar and Regev (2001) gave a general upper bound of 13/8 = 1.625 for any
number of bins.

  * •

Azar and Regev (2001) showed that, if the number of bins is between $3$ and
$21$, then there exists an algorithm with stretching factor
$\frac{5m-1}{3m+1}$.

  * •

Böhm et al. (2017) improved the upper bound for 3 bins to 11/8 = 1.375, and
improved the upper bound for any number of bins to $3/2$.

  * •

Lieskovský (2022) improved several upper bounds through computer searches:
$31/22$ for 4 bins, $23/16$ for 5 bins, $19/13$ for 6 bins.

Table 1 and Figure 3 give a summary of the lower bounds and upper bounds on
$s^{*}$ that were found.

Bins | 2 | 3 | 4 | 5
---|---|---|---|---
Lower bound | $4/3^{1}$ | $112/82^{3}$ | $19/14^{2}$ | $19/14^{3}$
Decimal | 1.3334 | 1.3659 | 1.3571 | 1.3571
Upper bound | $4/3^{6}$ | $11/8^{3}$ | $31/22^{5}$ | $23/16^{5}$
Decimal | 1.3334 | 1.375 | 1.409 | 1.438

Bins | 6 | 7 | 8 | 9 $\dots\infty$
---|---|---|---|---
Lower bound | $19/14^{3}$ | $19/14^{3}$ | $19/14^{3}$ | $4/3^{1}$
Decimal | 1.3571 | 1.3571 | 1.3571 | 1.3334
Upper bound | $19/13^{5}$ | $3/2^{3}$ | $3/2^{3}$ | $3/2^{3}$
Decimal | 1.462 | 1.5 | 1.5 | 1.5

Table 1: Known lower and upper bounds

1 Azar and Regev (2001)
2 Gabay et al. (2017)
3 Böhm and Simon (2020)
4 Böhm et al. (2017)
5 Lieskovský (2022)
6 Kellerer et al. (1997)

Figure 3: Known lower and upper bounds

As one can see in Figure 3, the gap between upper and lower bound for $m=3$
bins is pretty tight, but there is still much uncertainty about where $s^{*}$
really stands for $m\geq 4$.

With everything that was exposed previously, it is now possible to construct a
rudimentary algorithm to try to find lower bounds (Gabay et al., 2017). To do
so, we still need the following definitions:

######  Definition 2.1 (Packing).

We define a packing by a vector $b=(b_{1},\dots,b_{m})^{T}\in\mathbb{N}^{m}$
such that:

$b_{1}\geq b_{2}\geq\dots\geq b_{m}\geq 0$

We also write:

$||b||_{1}=\sum_{i=1}^{m}b_{i}$

A packing corresponds to a filling of the bins. Since all bins are equivalent,
we avoid symmetries by having the bins in a packing given by non increasing
order.

Let us note $e_{i}$ the vector with a 1 on the $i$-th coordinate and 0
elsewhere. If the bins have loads corresponding to a packing $b$, and an item
$y$ is then placed into some bin $i$, we write the resulting packing
$b^{\prime}=b+y\cdot e_{i}$. This is an abuse of notation, as a packing is
defined as having all coordinates non increasing. Doing this operation when
considering packings as vectors does not necessarily conserve this property.
However, we consider that this operation also rearranges the coordinates so
that the result is still a packing.

A packing does not correspond to a unique state in the 2 player game; all the
items that were previously given must also be considered. For example, with
two bins of capacity 3, the packing $(2,2)$ could be obtained after two
objects of size 2, or after two objects of size 1 and one object of size 2. In
the first case, the adversary can only send an item of size 1, while in the
second, the adversary can send an item of size 2. So considering only packings
isn’t sufficient: each possible game state corresponds to both an instance
(items that were sent) and a corresponding packing (loads of the bins). We
call a configuration such a game state:

######  Definition 2.2 (Configuration).

We define a configuration to be a pair $(I,b)$, with $I=(x_{1},\dots,x_{k})$
corresponding to the set of items that were given and $b$ corresponding to a
packing of the bins. A configuration $(I,b)$ must verify:

  * •

$(\frac{x_{1}}{g},\dots,\frac{x_{k}}{g})\in\mathcal{I}_{BS}$

  * •

$b$ is a packing

  * •

$b$ should be "reachable" with the set of items $I$, that is to say:

$\exists\;(P_{1},\dots,P_{m})\text{ partition of }\\{1,\dots,k\\}\;|\;\forall
i\in\\{1,\dots,m\\}\;\sum_{j\in P_{i}}x_{j}=b_{i}$

It can be remarked that this 2-player game has only two outcomes: either the
algorithm or the adversary wins. This means that any configuration is either
won by the algorithm or the adversary.

We now have all the tools needed to construct a rudimentary foundation of an
algorithm to obtain lower bounds. Algorithm 1 and Algorithm 2 form an example
of what an implementation could look like. However, without adding efficient
pruning, this algorithm will probably not be useful to obtain any new results.
The two functions in the pseudo-code below simulate the players "adversary"
(which sends items) and "algorithm" (which places items in bins).

Algorithm 1 Function adversary_to_play

1:Input: Configuration $C=(I,b)$

2:Output: Boolean value, True if the bound $t/g$ was proved, False otherwise

3:for $y$ extension of $I$ do

4: $\nu\leftarrow$ algorithm_to_play$(C,y)$

5: if $\nu$ is True then

6: Return True

7: end if

8:end for

9:Return False

Algorithm 2 Function algorithm_to_play

1:Input: Configuration $C=(I,b)$ and item $y$

2:Output: Boolean value, True if the bound $t/g$ was proved when adding the
item y to the configuration $C$, False otherwise

3:for bin $i=1,2,\ldots,m$ do

4: Construct configuration $C^{\prime}=(I\oplus y,b+e_{i}\cdot y)$

5: if $b_{i}+y<t$ then

6: $\nu\leftarrow$ adversary_to_play($C^{\prime}$)

7: if $\nu=False$ then

8: Return False

9: end if

10: end if

11:end for

12:Return True

In the previous algorithms, for simplicity, the method to find all possible
extensions of an instance (line 3 of the first algorithm) isn’t explained.
This will however be detailed in Section 4.

A simple improvement of the previous algorithms is to use a hash table to
store all configurations that were already explored. Böhm and Simon (2020)
proposed Zobrist hashing. On one hand, using hash tables yields a strong
increase in search speed but on the other hand, this optimization may also
require a large amount of memory, and especially so when the number of bins
$m$ and the capacity $g$ increase.

The game trees on which such lower bounds are found have humongous size; lower
bounds may also take long computation time to be found. We will propose in the
next sections new methods to speed up the searches, in order to find better
lower bounds.

##  3 Algorithm-winning packings pruning method

As explained previously, a game state is represented by both a packing (the
loads of the bins) and an instance (the set of items that were given). It can
be observed that if the player "algorithm" manages to reach certain packings,
the adversary will never be able to win - we won’t be able to prove the lower
bound $\frac{t}{g}$. For example, with two bins ($m=2$) each of capacity $g=6$
while trying to prove the bound $\frac{8}{6}$, if we reach the packing
$b=(6,5)^{T}$ then the adversary can only give an item of size $1$ which the
algorithm can place in any of the bins without reaching $t=8$; the packing
$(5,5)^{T}$ is also always winning for the algorithm, since only one item of
size $2$ or two items of size $1$ can be given, reaching the states $(7,5)$ or
$(6,6)$.

Knowing if a packing is always winning for the algorithm allows us to stop
exploring right away upon reaching this packing.

######  Definition 3.1 (Algorithm-winning packing).

A packing $b$ is said to be algorithm-winning if the algorithm always wins
upon reaching this packing, regardless of what items were given beforehand by
the adversary. We note $P_{alg}$ the set of algorithm-winning packings. More
formally:

Let $b$ be a packing. If $\forall I\in\mathcal{I}_{BS}$ such that $(I,b)$ is a
configuration, and that this configuration $(I,b)$ is winning for the
algorithm, then $b\in P_{alg}$.

We propose here a simple criterion to decide quickly for some packings if they
are always winning for the algorithm. Stronger versions of this criterion were
given by Böhm and Simon (2020), labelled as "good situations". However, we use
this criterion for its simplicity and we will build on the idea to construct
another property which is even stronger than what was proposed by Böhm and
Simon (2020).

######  Property 3.1.

Let $b$ be a packing. We remind here that the coordinates of $b$ are sorted in
non increasing order, so $b_{1}\geq b_{2}\geq\dots\geq b_{m-1}\geq b_{m}$.

$\left(b_{1}<t\text{ and }b_{m-1}>\frac{mg-t}{m-1}\right)\implies b\in
P_{alg}$

We will first provide an intuition of why this lemma is true through an
example. Let us consider 2 bins of capacity 6 and let’s try to prove the bound
8/6. It is possible to give a geometric representation of the packing as in
Figure 4.

Figure 4: Geometric representation of packings, for $m=2$, $t=8$ and $g=6$
(red: algorithm winning packings, green: adversary winning packings)

Each packing corresponds to a cell in the grid. The black area corresponds to
packings where the total load is strictly bigger than 12, which is impossible
since all the items given must fit into $2$ bins of size 6. The green areas
correspond to packings where at least one bin has load over 8 - hence the
adversary always win when reaching a green packing.
From a certain packing, when adding an item to any bin, it can only increases
one coordinate of the packing. It can be seen in the figure that for any
packing in the red area, it will never be possible to reach a green packing.
Hence the adversary is never able to prove the bound when such a red packing
is reached; so the red area corresponds to algorithm-winning packings.

Figure 5: A geometric representation of packings (hatched area corresponds to
algorithm-winning packings)

Let us now take a look at the hatched area in the Figure 5. If a packing from
this area is reached, then the algorithm can always decide for the next items
to go in the direction of the red area. Eventually, the red area will be
reached, and the algorithm will win. So the hatched area also corresponds to
algorithm-winning packings.

###### Proof.

We now begin a formal proof of Property 3.1. Let $b=(b_{1},\dots,b_{m})$ be a
packing, with $b_{1}<t$. Let us remark that if placing all the remaining items
in $b_{m}$ does not reach at least $t$, then the bound cannot be proven; i.e.
$b_{m}+mg-||b||_{1}<t\implies b\in P_{alg}$. The lefthand side of the
implication is equivalent to $mg-t<||b||_{1}-b_{m}$.
Yet $||b||_{1}-b_{m}=\sum_{i=1}^{m-1}b_{i}\geq(m-1)b_{m-1}$. So if
$(m-1)b_{m-1}>mg-t$, then $b_{m}+mg-||b||_{1}<t$; hence the bound cannot be
proven, and $b\in P_{alg}$. ∎

This criterion isn’t that strong, in the sense that it does not cover enough
packings to significantly speed up the search for lower bounds, and especially
so when the number of bins increases. We propose the following idea to
increase the number of packings that are always winning for the algorithm: it
is possible to propagate the algorithm-winning packings.

If from one packing, for all possible item sizes $s$ that can be given, it is
always possible to put the item in a bin $i$ to reach an algorithm-winning
packing, then the packing is also algorithm-winning. The biggest item size
that could be given is exactly $\min\\{g;\;mg-||b||_{1}\\}$, because we know
that the sum of item sizes is smaller than $mg$ and that each item must
individually be smaller than $g$.

Figure 6: Illustration of the propagation of algorithm-winning packings

Let us look at an example with $2$ bins of capacity $6$ while trying to prove
the bound $8/6$. In Figure 6, the packing (4, 1) can’t be decided to be
algorithm-winning with the previous critieria. However, if an item of size 1,
2 or 3 is given, this item could be placed in the first bin and an algorithm-
winning packing, (5, 1), (6, 1) or (7, 1) would be reached. If an item of size
4, 5 or 6 is given, it could be placed in the second bin and once again, an
algorithm-winning packing, (5, 4), (5, 5) or (6, 5) would be reached. Hence,
no matter what the given item is, it is possible to place it in a certain bin
so that an algorithm-winning packing is reached. This means that the packing
(4, 1) is also algorithm-winning. Then, we can also use the new information
that this packing (4, 1) is algorithm-winning to propagate even more packings!
Let us now properly present this idea through the following lemma:

######  Property 3.2.

Let $b$ be a packing, and $s_{max}=\min\\{g;\;mg-||b||_{1}\\}$ be the maximum
size of an item that could be given from this packing. Then:

$(\,\forall s\in\\{1,\dots,s_{max}\\},\;\exists\;1\leq i\leq m\;\text{such
that}\;b+s.e_{i}\in P_{alg})\,\implies(b\in P_{alg})$

with $e_{i}$ being the vector with a 1 on the $i$-th coordinate and 0
elsewhere.

###### Proof.

Upon reaching a packing $b$ satisfying this condition, no matter what item is
sent next, it is possible to place it in a bin to reach a new configuration
where the algorithm always wins. Hence the algorithm also always wins from the
packing $b$. ∎

This lemma allows to propagate algorithm-winning packings. We can first
identify some algorithm-winning packings with the use of the Property 3.1,
then apply Property 3.2 to propagate algorithm-winning packings.

Figure 7: Propagation of algorithm-winning packings using Property 3.2

Figure 7 is an example of what the propagation looks like for $m=2$, $g=6$,
$t=8$.

It is actually possible to improve this propagation idea: in some packings,
the adversary may need to send a big object to "jump" over algorithm-winning
packings; as such, during the tree-search, if this big object can’t be sent by
the adversary, then we already know that the algorithm wins. Moreover, it can
be observed that, the further the game goes, the more the player adversary is
restricted in the items he can give. Hence, if at some point the adversary
can’t send a certain size of item, then he will never be able to send this
size for the rest of the game.
Using this idea, it is possible to propagate as well a required item size for
each packing: if the player adversary, upon reaching a packing, can’t send at
least the required size of this packing, then the bound can’t be proven.

Here is an example of this idea. Let us look at Figure 7, and try to prove the
bound $8/6$ with $2$ bins. If we consider the packing (4, 4), we need to send
an item of size at least $4$ to not give the possibility to the algorithm to
go into an algorithm-winning packing.
In the packing (4, 3) we need to send an item of size at least $5$.
In the packing (4, 2), at least $6$.
In the packing (3, 2), if we send an item of size between 2 and 5, the
algorithm can choose to go to an algorithm-winning packing. So an item of size
either 1 or 6 must be sent. However, if the adversary cannot send an item of
size 6 and sends an item of size 1, the algorithm could choose to place the
item in the first bin, thus reaching the packing $(4,2)$, which requires an
item of size 6. The adversary can’t send an item of size 6 since he couldn’t
do that previously - so the algorithm wins.

We now properly present this idea, and also merge it with the previous
propagation idea.

######  Definition 3.2 (Minimum biggest extension).

We define the following function $v$ on packings such that if the adversary
can’t send at least $v(b)$ on the packing $b$, then the algorithm is winning.
On packings which are known to be algorithm-winning packings (using the
algorithm-winning propagation idea), we fix $v(b)=g+1$ to be consistent with
the previous definition of $v$.

  * •

If $b_{1}\geq t$, $v(b)=0$ (the bound $\frac{t}{g}$ is proved)

  * •

Else, if $||b||_{1}=mg$ then $v(b)=g+1$
The adversary can’t send anymore items, and the bound has not been proved, so
the algorithm wins

  * •

Else, if $b_{m-1}\geq\lceil\frac{mg-t}{m-1}\rceil+1$, $v(b)=g+1$
(according to the previous theorem, this packing is algorithm-winning)

  * •

Otherwise, we note $s_{max}=\min\\{g;\;mg-||b||_{1}\\}$ be the maximum item
size that could be given from the packing $b$, and:

$v(b)=\min_{s\leq s_{max}}\;\max_{i\leq m}\;\;\max\\{s;v(b+s\cdot e_{i})\\}$

######  Theorem 3.3.

If from the configuration $(I,b)$, the adversary is not able to send an item
of size at least $v(b)$ then the algorithm wins.

In other words, if $(I,b)$ is a configuration and $v(b)\neq 0$, then:

$v(b)\text{ is not an extension of I }\implies(I,b)\text{ is a winning
configuration for the algorithm}$

###### Proof.

Let us prove this theorem by induction on $||b||_{1}$ non increasing.

If $||b||_{1}=mg$, then the adversary cannot send any more items. Either
$b_{1}\geq t$, then $v(b)=0$; or the largest bin has load strictly below $t$
and the adversary can’t send anymore items, so $v(b)=g+1$. In both cases, the
theorem is true.

Now, let $b$ be a packing with $v(b)\neq 0$ and let us suppose that this
theorem was proved for all $b^{\prime}$ such that
$||b^{\prime}||_{1}>||b||_{1}$. We then note
$s_{max}=\min\\{g;\;mg-||b||_{1}\\}$ to be the maximum item size that could be
given from the packing $b$.

Let $I\in\mathcal{I}_{BS}$ be an instance such that $v(b)$ is not an extension
of $I$. Let us prove that no matter what item is sent from the configuration
$(I,b)$, there exists a bin such that placing the item in this bin results in
a win for the player algorithm.

We define $y_{max}=\max\\{y\text{ extension of }I\\}$, the biggest item that
can be sent from the configuration $C=(I,b)$. We then have according to the
previous hypothesis $y_{max}<v(b)$.
We have $y_{max}\leq s_{max}$, since any extension $y$ of $I$ must satisfy
$I\oplus y\in\mathcal{I}_{BS}$ which implies $\begin{cases}||b||_{1}+y\leq
mg\Leftrightarrow y\leq mg-||b||_{1}\\\ y\leq g\end{cases}$

So $y_{max}\leq\min\\{g;\;mg-||b||_{1}\\}=s_{max}$.

Let $y\in\\{1,\dots,y_{max}\\}$. By definition, $v(b)=\min_{s\leq
s_{max}}\;\max_{i\leq m}\;\;\max\\{s;v(b+s\cdot e_{i})\\}$. Let us write
$G_{y}(i)=\max\\{y;v(b+y\cdot e_{i})\\}$, and
$i_{max}=\operatorname*{arg\,max}G_{y}$.
We then have: $\forall y\leq y_{max}\;\;\;v(b)\leq G_{y}(i_{max})$.

Then, we show that placing the item $y$ in the bin $i_{max}$ wins for the
algorithm:
If $G_{y}(i_{max})=y$, then $v(b)\leq G_{y}(i_{max})=y\leq y_{max}<v(b)$,
which is a contradiction.
So we have $G_{y}(i_{max})=v(b+y\cdot e_{i})$. Let us note the configuration
$C^{\prime}=(I\oplus y,b+y\cdot e_{i_{max}})$. Then:

  1. 1.

$v(b)\leq G_{y}(i_{max})=v(b+y\cdot e_{i_{max}})$

  2. 2.

Since $v(b)$ is not an extension of $I$, then $v(b+y\cdot e_{i_{max}})\geq
v(b)$ is not an extension of $I$ hence not an extension of $I\oplus y$.

  3. 3.

By induction, as $v(b+y\cdot e_{i_{max}})$ is not an extension of $I\oplus y$,
the algorithm always wins from the configuration $C^{\prime}$.

So for any item $y$ that can be sent, placing the item in the bin
$i_{max}=\operatorname*{arg\,max}G_{y}$ results in a configuration that is
winning for the algorithm, which concludes the proof.

∎

To compute $v(b)$, we proceed by non increasing values of $||b||_{1}$,
starting with $||b||_{1}=mg$.

To fully use the information in our tree search, we need to store for each
possible packing $b$ the associated value $v(b)$. Hence we need to know how
much memory to allocate in order to store all of the values $v(b)$, and thus
we would like to know how many packings there are. If there wasn’t the
constraint forcing the coordinates to be non increasing, a possible upper
bound of this number could be $t^{m}$ possible packings since each bin could
have $t$ different possible values (from 0 to $t-1$). However, we can be much
more efficient than this by using symmetries, which is the object of what
follows.

######  Notation 3.4.

Let $k\in\mathbb{N}^{*}$ and $n\in\mathbb{N}^{*}$. We write $P_{k,n}$ the set
of packings over $n$ bins such that each coordinate is strictly less than $k$
:

$P_{k,n}=\\{(b_{1},\dots,b_{n})\in\mathbb{N}^{n}\;|\;k>b_{1}\geq
b_{2}\geq\dots\geq b_{n}\geq 0\\}$

We moreover define $N_{k,n}$ to be the cardinality of the previous set:

$N_{k,n}=|P_{k,n}|$

We aim to compute $N_{t,m}$ to know how much memory we will need to store each
value $v(b)$.

######  Property 3.5.

Let $k\in\mathbb{N}^{*}$ and $n\in\mathbb{N}^{*}$. Then the number of packings
over $n$ bins such that each coordinate is strictly less than $k$ is exactly:

$N_{k,n}=\binom{k+n-1}{k-1}=\frac{k(k+1)(\dots)(k+n-1)}{n!}$

The proof of this result is given in Appendix 7.1.

With the previous result we can compute the number of packings $N_{t,m}$, and
we know how much memory we need to store all the values of $v(b)$. We now only
need a bijection, which we will call $ind_{m}$, from $P_{t,m}$ to the integers
between $0$ and $\binom{t+m-1}{t-1}-1$. With such a bijection, we can store
all the values $v(b)$ in a table, such that the value $v(b)$ in the table is
at the index $ind_{m}(b)$.

We propose the following function:

######  Definition 3.3 (Index of a packing).

We define the index $ind_{m}(b)$ of a packing $b=(b_{1},\dots,b_{m})$ as
follows:

$ind_{m}(b)=\sum_{i=1}^{m}N_{b_{i},m-i+1}$

######  Property 3.6.

For any $t$, the function $ind_{m}$ is a bijection between $P_{t,m}$ and
$\left\llbracket 0,\binom{t+m-1}{t-1}-1\right\rrbracket$

The proof of this result is given in Appendix 7.2

This bijection allows us to store the function $v(b)$ for each $b$ in an
efficient manner. One can simply compute and store in a table all the
coefficients $N_{t^{\prime},m^{\prime}}$ for $t^{\prime}=1,\ldots,t$ and
$m^{\prime}=1,\ldots,m$. Then, a table of size $N_{t,m}$ can be allocated to
store the values of the function $v(b)$. To retrieve the information $v(b)$ of
a packing, one just needs to compute $ind_{m}(b)$ which corresponds to the
index in the table. This computation is done in $O(m)$.

It is possible to be even more precise than the previous analysis when
counting the number of packings. The previous counting method didn’t take into
account the constraint on packings that $||b||_{1}=\sum_{i=1}^{m}b_{i}\leq
mg$. This will be very useful in Section 4, to compute efficiently which items
can be sent from a given configuration. We will explain this more accurate
idea in Section 4.

##  4 Knowing which item can be sent next

The player adversary can only send items such that all the items can fit into
$m$ bins of size $g$ \- hence we must compute which items can be sent from
some state of the game. If an item can be sent, then according to Property
1.1, any smaller item can also be sent. So the problem is equivalent to
finding the largest item that can be sent from a game state. More formally, if
$(I,b)$ is a configuration corresponding to a game state, we want to compute:

$y_{max}=\max\\{y\text{ extension of }I\\}$

However, finding this value is a NP-hard problem (there is a simple reduction
from bin packing). Moreover, we have to compute this value at every game
state. This makes it critical to optimize its computation.

Previously, this problem was solved by calling an optimization solver (Gabay
et al., 2017). This has been improved in (Böhm and Simon, 2020) where a
combination of methods was used: lower and upper bounds, hash tables and
dynamic programming. The authors claimed their approach was much faster than
using a solver. We propose here an even better method than what was proposed
so far, also using dynamic programming.

######  Notation 4.1.

Let $I$ be an instance. We write $\mathcal{B}_{I}=\\{b\text{ packing
}|(I,b)\text{ configuration and }b_{1}\leq g\\}$.

Computing the largest extension of an instance $I$ can be done by considering
the set $\mathcal{B}_{I}$:

######  Property 4.2.

The biggest item $y_{max}$ that can be sent from a configuration $(I,b)$ is:

$y_{max}=\max_{b\in\mathcal{B}_{I}}\\{g-b_{m}\\}$

###### Proof.

Let us note $I=(x_{1},\dots,x_{k})$.

For any packing $b\in\mathcal{B}_{I}$, the value $g-b_{m}$ is an extension of
$I$, since the item $g-b_{m}$ can be placed in the bin $b_{m}$. So

$y_{max}\geq\max_{b\in\mathcal{B}_{I}}\\{g-b_{m}\\}$

Finally, we show that

$y_{max}\leq\max_{b\in\mathcal{B}_{I}}\\{g-b_{m}\\}$

Since $y_{max}$ is an extension of $I$, then there is a partition of the
objects $(x_{1},\dots,x_{k},y_{max})$ in $m$ bins of capacity $g$. Let us
construct the packing $b$ by packing only the items from $I$ according to the
partition. Then, by definition $b\in\mathcal{B}_{I}$. Moreover, $y_{max}$ can
be placed in a bin with load $b_{i}\geq b_{m}$ of $b$. So $b_{m}+y_{max}\leq
b_{i}+y_{max}\leq g$, and then:

$y_{max}\leq g-b_{m}$

Since $b\in\mathcal{B}_{I}$, we have:

$y_{max}\leq\max_{b\in\mathcal{B}_{I}}\\{g-b_{m}\\}$

which concludes the proof. ∎

We now explain the dynamic programming method to find the largest extension of
an instance.

Let $I=(x_{1},\dots,x_{k})$ be an instance. Let us note
$I_{i}=(x_{1},\dots,x_{i})$ for $i=1,\dots,k$ and $I_{0}=\emptyset$ be the
empty instance. To compute the biggest extension of $I$, the dynamic program
construct the sets of packings $\mathcal{B}_{I_{i}}$ as follows:

  * •

$\mathcal{B}_{I_{0}}=\\{(0,\dots,0)\\}$

  * •

For $1\leq i\leq k$, $\mathcal{B}_{I_{i}}=\\{b+x_{i}\cdot e_{j}\text{ such
that }b\in\mathcal{B}_{I_{i-1}},\;b_{j}+x_{j}\leq g\text{ and }j\in\llbracket
1,m\rrbracket\\}$

In other words, for any packing $b$ in $\mathcal{B}_{I_{i-1}}$, we look at all
the packings formed when adding to $b$ the item $x_{i}$ into a bin. We only
keep the packings where all bins have loads equal or smaller than $g$. The set
$\mathcal{B}_{I_{i}}$ can then be constructed by the union of all of those
packings. This allows us to compute the set $\mathcal{B}_{I}$. We can then
find $\max_{b\in\mathcal{B}_{I}}\\{g-b_{m}\\}$; with Property 4.2 this is
equal to the largest extension of $I$.

This method, however, poses several problems when trying to actually implement
it.

  1. 1.

We do not know the cardinality of $\mathcal{B}_{I_{i}}$, which prevents us to
allocate memory in an efficient manner.

  2. 2.

We need a way to prevent a single packing to be added to a set
$\mathcal{B}_{I_{i}}$ several times.

To deal with the second problem, Böhm and Simon (2020) used a hash table.
However, we propose another idea. We first tackle the first problem by
counting the exact number of packings in $\mathcal{B}_{I}$, which is the
object of what follows; we will then show that counting also results in a
solution to the second problem. The approach is similar to the counting
arguments given in Section 3, but is a bit more complex and more accurate.

Let $I=(x_{1},\dots,x_{k})$ be an instance. We first aim to compute the number
of packings that can be in the set $\mathcal{B}_{I}$.

######  Notation 4.3.

Let $S\geq 0$, $k\geq 0$ and $n\geq 1$ be integers. We write $P_{S,k,n}$ the
set of packings over $n$ bins such that each coordinate is smaller or equal to
$k$ and that the sum of the coordinates is exactly $S$:

$P_{S,k,n}=\left\\{(b_{1},\dots,b_{n})\in\mathbb{N}^{n}\;\text{such that
}\begin{cases}k\geq b_{1}\geq\dots b_{m}\\\ ||b||_{1}=S\end{cases}\right\\}$

We also write $N_{S,k,n}=|P_{S,k,n}|$.

We can remark that any packing $b\in\mathcal{B}_{I}$ satisfies
$||b||_{1}=||I||_{1}$, with $||I||_{1}$ being the sum of items of the
instance. Hence, $\mathcal{B}_{I}\subseteq P_{||I||_{1},g,m}$. Computing
$N_{||I||_{1},g,m}$ then gives us an upper bound on the cardinality of
$\mathcal{B}_{I}$. This will allow us to know how much memory we need to store
the set $\mathcal{B}_{I}$.

######  Property 4.4.

$N_{S,k,1}=\begin{cases}1\text{ if }k\geq S\\\ 0\text{ otherwise}\end{cases}$

If $n>1$, then:

$N_{S,k,n}=\sum_{i=1}^{\min\\{k,S\\}}N_{S-i,i,n-1}$

By convention, if $k=0$ then the sum in the right hand side of the equation
above is 0.

###### Proof.

With only 1 bin, if $k\geq S$, then $P_{S,k,1}=\\{(S)\\}$. Otherwise, the set
is empty.

If $n>1$: We look at all the possibilies for the first coordinate of the
packing, which corresponds to the variable $i$ in the equation. Then, the sum
of the leftover coordinates must be equal to $S-i$, hence the formula. In a
more formal way:

$P_{S,k,n}=\bigcup_{i=1}^{min\\{k,S\\}}\\{(i,b_{2},\dots,b_{n})\text{ such
that }(b_{2},\dots,b_{n})\in P_{S-i,i,n-1}\\}$

Since all sets in the union are disjoints, we obtain the result presented in
Property 4.4. ∎

We have not found an explicit formula for $N_{S,k,n}$ in the general case.
However, Property 4.4 still allows us to compute this coefficient rather
efficiently. We propose to store all of the coefficients $N_{S,k,n}$ for
$S=0,\ldots,mg$, $k=0,\dots,g$ and $n=1,\dots,m$ in a table. This only
corresponds to $(mg+1)(g+1)(m)\approx m^{2}g^{2}$ coefficients which isn’t
large for the bounds we aim to improve: if $m=10$, $g=200$, this corresponds
to roughly $4\times 10^{6}$ which is a very manageable number of integers to
store for a computer.

Now that we know an upper bound of the cardinality of $\mathcal{B}_{I}$, we
would like to address the second issue described earlier. We are constructing
a set $\mathcal{B}_{I}$ by adding elements to this set one by one. To prevent
duplicates, we want to construct a bijection between possible packings of this
set and natural integers.

######  Property 4.5.

Let $S\in\mathbb{N}$. We construct the function
$f\;:\;P_{S,g,m}\rightarrow\llbracket 0,N_{S,g,m}-1\rrbracket$ as follows:

If $S=0$, $f(b)=0$.

Otherwise, let $b\in P_{S,g,m}$. Let $r$ be the index of the smallest bin of
$b$ that is not empty: $b_{r}\neq 0$ and either $r=m$ or $b_{r+1}=0$. We also
note $S_{i}=S-\sum_{j=1}^{i}b_{j}$.

We define

$f(b)=\sum_{i=0}^{r-1}N_{S_{i},b_{i+1}-1,m-i}$

Then $f$ is a bijection.

###### Proof.

Let’s define $<_{lex}$ the lexicographical order on packings. We will show
that $f(b)=|\\{b^{\prime}\in P_{s,g,m}\;|\;b>_{lex}b^{\prime}\\}|$.

If $S=0$ then only $b=(0,\dots,0)$ is in the domain of $f$; $f(b)=0$, and
there are no packings smaller with the lexicographical order than $b$.

Otherwise, for $1\leq i\leq r-1$, the coefficient $N_{S_{i},b_{i+1}-1,m-i}$
corresponds precisely to the number of packings of $P_{S,g,m}$ that have
exactly the first $i$ coordinates equal to the first $i$ coordinates of $b$
and that are stricly smaller lexicographically than $b$. Since the first $i$
coordinates are equal to those of $b$, the rest of the coordinates sums to
$S_{i}$.

Hence, $f$ is indeed a bijection. ∎

Using this bijection, it is possible to check quickly whether or not a packing
was already added to a set $\mathcal{B}_{I}$. We propose to have a boolean
table of size $N_{||I||_{1},g,m}$, initialized at False everywhere. Whenever
we add a packing $b$ to $\mathcal{B}_{I}$, we first check whether or not this
packing is already in the table by looking at index $f(b)$ of the boolean
table. If the result is True, we already added $b$ in the set
$\mathcal{B}_{I}$. Otherwise, we set the value in the boolean table to True,
and we add the packing to the set.

During the search for a lower bound, at a certain configuration $(I,b)$, we
keep in a table the set $\mathcal{B}_{I}$. When proposing an item $y$, we can
quickly construct the new set $\mathcal{B}_{I\oplus y}$ from the previous
$\mathcal{B}_{I}$. Böhm and Simon (2020) had to construct the set
$\mathcal{B}_{I\oplus y}$ from scratch everytime, while here we only have to
do one iteration of the dynamic program.

##  5 Results

All our results have been computed on a computer with an Intel Core i5-4690
CPU and 15.6GiB of RAM. Our code is available
online111https://github.com/lhommeant/Lower-bound-for-online-bin-stretching.

With the improvements presented in the previous sections, we managed to prove
3 new lower bounds:

######  Theorem 5.1.

$\frac{15}{11}\text{ is a lower bound of }s^{*}\text{ for 6, 7 and 8 bins.}$

For 6, 7 and 8 bins, the previous lower bound was $19/14\approx 1.3571$ while
the new bound is approximately $1.3636$.

We compare now the time needed by our method to prove some bounds. The search
method for lower bounds was improved and is faster in some cases than the
implementation proposed by Böhm and Simon (2020). However, it is hard to
compare times given by Böhm and Simon (2020) with ours, because of the
following reasons:

  * •

Most times given by Böhm and Simon (2020) can’t be compared, because they
correspond to the search time while knowing some information on the solution
(this information is called the monotonicity by Böhm and Simon (2020)). This
information makes it much easier to find a solution.

  * •

Böhm and Simon (2020) used parallel computation to obtain certain results.

  * •

Böhm and Simon (2020) used better hardware.

In Table 2 we compare our approach, for information purposes only, to the
times given when this additional ’monotonicity’ information isn’t known. The
row "Bound valid" determines if the corresponding lower bound is valid or not.
We add a $(p)$ if the result from Böhm and Simon (2020) was obtained after
parallel computation.

Bins | 3 | 3 | 3 | 3 | 4
---|---|---|---|---|---
Lower bound | 19/14 | 30/22 | 55/40 | 56/41 | 19/14
Time from Böhm and Simon (2020) | 2s. | 6s. | 3min. 6s. | 30min. | 18s.(p)
Our time |  $<0.1$s | 0.1s | 5s. | 13s. | 0.1s
Bound valid | Yes | No | No | No | Yes

Bins | 4 | 4 | 6 | 7 | 8
---|---|---|---|---|---
Lower bound | 30/22 | 34/25 | 15/11 | 15/11 | 15/11
Time from Böhm and Simon (2020) | 19s.$(p)$ | 48s$(p)$. | - | - | -
Our time | $18s$ | 2min. 24 | 14s. | 1min. 52s. | 1h.
Bound valid | No | No | Yes | Yes | Yes

Table 2: Time comparison between Böhm and Simon (2020) and our implementation

It can be seen in Table 2 that while our approach is much faster than the
sequential algorithm by Böhm and Simon (2020), this is no longer true when
comparing our implementation to the parallel one given by Böhm and Simon
(2020). However, our algorithm is still able to be quite competitive. A
possibility could be to parallelize our implementation in order to even
further improve the bounds.

Lastly, Figure 8 shows our contribution to lower bounds in a graphical manner.

Figure 8: Improved lower bound

##  6 Conclusion and perspectives

This article presented an online problem and an approach based on
computational search to find lower bounds on the performance of online
algorithms for the problem. We gave new ideas to improve the efficiency of the
method to find lower bounds, and implemented them, which resulted in the
improvement of three lower bounds. The search speed of the method to obtain
bounds was increased as well.

In order to improve the bounds of the online bin stretching problem even
further, several things could be envisioned: our implementation could be
parallelized, the algorithm to find bounds could be run for longer and on
better computers and perhaps stronger pruning ideas similar to the ones
presented here could be found.

We believe that this computational approach to find bounds could be
generalized to many other online problems. One could start by considering
problems closely related to online bin stretching: by changing the guarantee
that the items fit into $m$ bins into another constraint, by changing the
objective into the ratio of performance between an online algorithm and the
optimal offline algorithm…

##  7 Appendix

We give here several proofs that were not developped in the previous sections.

###  7.1 Proof of Property 3.5

In order to prove Property 3.5, we need to use the following result, known as
the hockey-stick identity:

######  Lemma 7.1 (Hockey-stick identity).

Let $(n,r)\in\mathbb{N}^{2}$ such that $n\geq r$. Then:

$\binom{n+1}{n-r}=\sum_{j=0}^{n-r}\binom{j+r}{r}=\sum_{j=0}^{n-r}\binom{j+r}{j}$

The proof of this classical identity is not included here, but can be found
online222https://en.wikipedia.org/wiki/Hockey-stick_identity.

###### Proof.

Let us prove Property 3.5;

First, we remark that:

  * •

If $n=1$ then $N_{k,1}=k$

  * •

Otherwise, $N_{k,n}=\sum_{i=0}^{k-1}N_{i+1,n-1}$

The second point is proved as follows:
$P_{k,n}=\bigcup_{b_{1}=0}^{k-1}\\{(b_{1},b_{2},\dots,b_{n})|b_{1}\geq
b_{2}\geq\dots\geq b_{n}\geq 0\\}$
All sets in this union are disjoints. Hence:

$|P_{k,n}|=\sum_{b_{1}=0}^{k-1}|\\{(b_{1},b_{2},\dots,b_{n})|b_{1}\geq
b_{2}\geq\dots\geq b_{n}\geq 0\\}|=\sum_{i=0}^{k-1}N_{i+1,n-1}$

With this remark, we can now prove the Property 3.5 by induction on $n$. If
$n=1$, then $N_{k,1}=k=\binom{k+n-1}{k-1}$, so the theorem is true.
Let us now suppose that the theorem is true for $n-1$, and let’s prove it for
$n$. Then:

$N_{k,n}=\sum_{i=0}^{k-1}N_{i+1,n-1}=\sum_{i=0}^{k-1}\binom{i+n-1}{i}$

Applying the hockey stick identity, we obtain that:

$\sum_{i=0}^{k-1}\binom{i+n-1}{i}=\binom{k+n-1}{k-1}$

So $N_{k,n}=\binom{k+n-1}{k-1}$. ∎

###  7.2 Proof of Property 3.6

We prove here Property 3.6.

###### Proof.

We show that the function $ind_{m}$ is a bijection by induction on $m$. Let
$t\in\mathbb{N}^{*}$.
If $m=1$, let $b\in P_{t,1}=(b_{1})$ then $ind_{1}(b_{1})=N_{b_{1},1}=b_{1}$.
So $ind_{1}$ is indeed a bijection between $P_{t,m}$ and $\left\llbracket
0,\binom{t+m-1}{t-1}-1\right\rrbracket$.

Let us suppose that $\forall m^{\prime}<m$ the function $ind_{m^{\prime}}$ is
a bijection between $P_{t,m^{\prime}}$ and $\left\llbracket
0,\binom{t+m^{\prime}-1}{t-1}-1\right\rrbracket$.

Let $b\in P_{t,m}$. Then:

$ind_{m}(b)=\sum_{i=1}^{m}N_{b_{i},m-i+1}=N_{b_{1},m}+ind_{m-1}((b_{2},\dots,b_{m}))$

By convention, we write $\binom{n}{-1}=0$.
Yet by induction, $ind_{m-1}$ is a bijection between $P_{b_{1}+1,m-1}$ and
$\left\llbracket 0,\binom{b_{1}+m-1}{b_{1}}-1\right\rrbracket$. Let us note

$I_{b_{1}}=\left\llbracket\binom{b_{1}+m-1}{b_{1}-1},\binom{b_{1}+m-1}{b_{1}-1}+\binom{b_{1}+m-1}{b_{1}}-1\right\rrbracket$

which simplifies to

$I_{b_{1}}=\left\llbracket\binom{b_{1}+m-1}{b_{1}-1},\binom{b_{1}+m}{b_{1}}-1\right\rrbracket$

Then $\begin{cases}P_{b_{1}+1,m-1}\rightarrow I_{b_{1}}\\\
(b_{2},\dots,b_{m})\mapsto ind_{m-1}(b_{2},\dots,b_{m})\end{cases}$ is also a
bijection.

To conclude the proof, we just need to prove that all the sets $I_{b_{1}}$ are
disjoints. Let us write $h(b_{1})=\binom{b_{1}+m-1}{b_{1}-1}$.

Then $I_{b_{1}}=\llbracket h(b_{1}),h(b_{1}+1)-1\rrbracket$. To prove that the
sets are disjoints we then just need to prove that the function $h$ is
strictly increasing:

  * •

If $b_{1}>0$, then $\frac{h(b_{1}+1)}{h(b_{1})}=\frac{b_{1}+m}{m}>1$

  * •

If $b_{1}=0$, then $h(0)=0<h(1)=1$

So $h$ is strictly increasing. So the sets $I_{b_{1}}$ are all distinct.

So the function $\begin{cases}P_{t,m}\rightarrow\left\llbracket
0,\binom{t+m-1}{t-1}-1\right\rrbracket\\\ b\mapsto ind_{m}(b)\end{cases}$ is a
bijection. ∎

## References

  * Azar and Regev (2001) Azar, Y., Regev, O., 2001.  On-line bin-stretching.  Theoretical Computer Science 268, 17–41.  URL: https://www.sciencedirect.com/science/article/pii/S0304397500002589, doi:https://doi.org/10.1016/S0304-3975(00)00258-9. on-line Algorithms ’98.
  * Böhm et al. (2017) Böhm, M., Sgall, J., van Stee, R., Veselý, P., 2017\.  A two-phase algorithm for bin stretching with stretching factor 1.5.  Journal of Combinatorial Optimization 34, 810–828.  URL: https://doi.org/10.1007/s10878-017-0114-4, doi:10.1007/s10878-017-0114-4.
  * Böhm and Simon (2020) Böhm, M., Simon, B., 2020.  Discovering and certifying lower bounds for the online bin stretching problem.  arXiv:2001.01125.
  * Gabay et al. (2017) Gabay, M., Brauner, N., Kotov, V., 2017.  Improved lower bounds for the online bin stretching problem.  4OR 15, 183–199.  URL: https://doi.org/10.1007/s10288-016-0330-2, doi:10.1007/s10288-016-0330-2.
  * Kellerer et al. (1997) Kellerer, H., Kotov, V., Speranza, M.G., Tuza, Z., 1997\.  Semi on-line algorithms for the partition problem.  Operations Research Letters 21, 235–242.  URL: https://www.sciencedirect.com/science/article/pii/S0167637798000054.
  * Lieskovský (2022) Lieskovský, M., 2022.  Better algorithms for online bin stretching via computer search.  URL: https://arxiv.org/abs/2201.12393, doi:10.48550/ARXIV.2201.12393.