Online Bin Stretching is a semi-online variant of Bin Packing with a set number of m bins, where all bins can be overpacked to capacity S 1, which is to be minimized. There is also a guarantee that an offline algorithm can pack the input to m bins of unit size. We focus on the problem of Online Bin Stretching for small m, namely 3 m 5. Recent progress on this problem has led into a lower bound of 19=14 1:357 for m = 3 and an upper bound of 11=8 = 1:375 for the same. For m = 4 and m = 5, only a trivial lower bound of 4=3 was known. We improve the techniques used in the previous lower bound for m = 3 to reach a lower bound of 45=33 = 1:36 for m = 3 and a new lower bound of 19=14 1:357 for m = 4 and m = 5.
1. The number of bins m is fixed at the start of the input. 2. There is a guarantee that an offline algorithm is able to pack any input into m bins of capacity 1. 3. The online algorithm for Online Bin Stretching can use bins of capacity S for some S 1. The goal is to minimize the parameter S, known as the stretching factor.
Even though Online Bin Stretching is described using bin packing
terminology, it is clear from the description that it is equivalent to the problem
of semi-online makespan minimization on m identical machines with a
guarantee that there exists a schedule with unit makespan. Therefore, Online Bin
Stretching is related to other semi-online scheduling problems, such as online
makespan minimization with a known sum of processing times [
The problem has been revisited recently, with algorithmic results from Kellerer
and Kotov [
We focus on the setting where the number of bins m is fixed and small. For m = 2, a lower and upper bound of 4=3 is easy and well-known.
The case m = 3 is the smallest case where the optimal stretching factor is
not yet known. The best current online algorithm is from [
The lower bound of [
For the case m = 4 and m = 5, the best online algorithm is from the original
paper by Azar and Regev [
Very recently and independently on our work, the authors of [
On the conceptual side, we propose a different algorithm for computing the
offline optimum packing, suggest new ways of pruning the game tree and show
how the alpha-beta pruning of [
On the technical side, we reimplement the algorithm of [
With these improvements, we were able to find an improved lower bound for Online Bin Stretching for three bins, namely 45=33 = 1:36.
We also present the first non-trivial lower bound of 19=14 1:357 for m = 4
and m = 5. (A lower bound for m = 4 is also independently presented in the
recently updated preprint [
To see the strength of our improvements, consider the granularity of the
items defined above as K. It is easy to see that a general game tree search is
exponential in the running time with respect to K. The algorithm of [
In contrast, our proposed algorithm is able to check all K 41 and is fast enough to produce results for m = 4 and m = 5.
The source code for the computer search as well as the complete results can be found at http://iuuk.mff.cuni.cz/ bohm/p/bs/lowerbound-sofsem.zip. Definitions and scaling. We now present a formal definition of the Online Bin Stretching problem on three bins. Throughout the text, we use the standard bin packing notions of size, load and capacity. Each item i has an associated size s(i) 2 R, usually integral or fractional. A load of a bin is the sum of the items currently packed into it. A capacity of a bin is the maximum load that it allows.
To make the problem easier for computer and human alike, we scale the bins so that the optimal bins have capacity T 2 N (instead of unit capacity) and the stretched bins have capacity S 2 N. The resulting stretching factor is then S=T . Definition 1. The problem Online Bin Stretching on three bins is defined as follows: Parameters: The limit of stretched bins S and the limit of the offline optimum bins T .
Input: A sequence of items I = i1; i2; : : : given online one by one. Each item has a size s(i) 2 (0; T ] and must be packed immediately and irrevocably. Output: Partitioning (packing) of I into the three bins B1; B2; B3 so that for all three bins it holds that Pi2Bj s(i) S.
Guarantee: there exists a packing of all items in I into 3 bins of capacity T . Goal: Design an online algorithm with the stretching factor S=T as small as possible which packs all input sequences satisfying the guarantee. 2
In Section 2 and 3, we describe our lower bound technique. To simplify our arguments, we describe the technique only for m = 3. We discuss the pecularities of the generalization to any fixed m in Section 5.
As with many other online algorithms, we can think of Online Bin Stretching as a two player game. The first player (Algorithm) is presented with an item i. Algorithm’s goal is to pack it into m bins of capacity S. This mimics the task of any algorithm for Online Bin Stretching. The other player (Adversary) decides which item to present to the Algorithm in the next step. The goal of the Adversary is to force Algorithm to overpack at least one bin.
It is clear that knowing the game tree for a parameter S of the aforementioned game is equal to knowing whether there is an algorithm for Online Bin Stretching with stretching factor S.
We are interested primarily in the lower bound. Therefore, it makes sense to slightly reformulate the previous game: – The player Algorithm wins if it can pack all items into bins with capacity strictly less than S. – The player Adversary wins if it can force Algorithm to pack a bin with load S while making sure that the Online Bin Stretching guarantee is satisfied.
This way, a victory for the player Adversary immediately implies that no online algorithm for Online Bin Stretching with stretching factor less than S exists.
The two main obstacles to implementing a search of the described two player game are the following:
2. Adversary needs to make sure that at any time of the game, an offline optimum can pack the items arrived so far into three bins of size T .
To overcome the first problem, it makes sense to create a sequence of games based on the granularity of the items that can be packed. A natural granularity for the scaled game are integral items, which correspond to multiples of 1=T in the non-scaled problem.
The second problem increases the complexity of every game turn of the Adversary, as it needs to run a subroutine to verify the guarantee for the next item it wishes to place.
Note that the ideas described above have been described previously in [
To precisely formulate our setting, we first define one state of a game: Definition 2. For given parameters S 2 N; T 2 N, a bin configuration is a tuple (a; b; c; I), where – a; b; c 2 f0; 1; : : : ; Sg denote the current sorted loads of the bins, – I is a multiset with ground set f1; 2; : : : ; T g which lists the items used in the bins.
Additionally, in a bin configuration, it must hold: – that there exists a packing of items from I into three bins with loads exactly a; b; c, – that there exists a packing of items from I into three bins that does not exceed T in any bin.
It is clear that every bin configuration is a valid state of the game with Adversary as the next player. We may also observe that the existence of an online algorithm for Online Bin Stretching implies an existence of an oblivious algorithm wit the same stretching factor that has access only to the current bin configuration B and the incoming item i.
Using the concept of bin configuration and the previous two facts, we may formally define the game we investigate: Definition 3. For a given S 2 N; T 2 N, the bin stretching game BSG(S; T ) is the following two player game: 1. There are two players named Adversary and Algorithm. The player
Adversary starts. 2. Each turn of the player Adversary is associated with a bin configuration B = (a; b; c; I). The start of the game is associated with the bin configuration (0; 0; 0; ;). 3. The player Adversary receives a bin configuration B. Then, Adversary selects a number i such that the multiset I [ fig can be packed by an offline optimum into three bins of capacity T . The pair (B; i) is then sent to the player Algorithm. 4. The player Algorithm receives a pair (B; i). The player Algorithm has to pack the item i into the three bins as described in B so that each bin has load strictly less than S. Algorithm then updates the configuration B into a new bin configuration, denoted B0. Algorithm then sends B0 to the player Adversary. 5. If the player Algorithm receives a pair (B; i) such that it cannot pack the item according to the rules, the bin configuration B is won for player Adversary. 6. If the player Adversary has no more items i that it can send from a configuration B, the bin configuration B is lost for player Adversary. 7. For any bin configuration B where the player Adversary has a possible move, the configuration is won for player Adversary if and only if the game ends in a bin configuration C that is won for the player Adversary no matter which decision is made by the player Algorithm at any point. Definition 4. We say that a game BSG(S; T ) is a lower bound if and only if the bin configuration (0; 0; 0; ;) is won for the player Adversary. 3
Our implemented algorithm is a fairly standard implementation of the minimax game search algorithm. The pecularities of our algorithm (caching, pruning, and other details) are described in the following sections.
One of the differences between our algorithm and the algorithm of Gabay
et al. [
Input is a bin configuration B = (a; b; c; I). (1) Check if the bin configuration is cached (Section 3.2); if so, output the value found in cache and return. (2) Create a list L of items which can be sent as the next step of the player
Adversary (Section 3.1). (3) For every item size i in the list L: (4) Recurse by running EvaluateAlgorithm(B; i). (5) If EvaluateAlgorithm(B; i) returns 0 (the configuration is won for player Adversary), stop the cycle and end EvaluateAdversary with value 0. (6) Otherwise, continue with the next item size. (7) If the evaluation reaches this step, store the configuration in the cache and return value 1 (player Algorithm wins).
Input is a bin configuration B = (a; b; c; I) and item i. (1) If applicable, prune the tree using known algorithms (Section 3.3). (2) For any one of the three bins: (3) If i can be packed into the bin so that its load is less than T : (4) Create a configuration B0 that corresponds to this packing. (5) Run EvaluateAdversary(B0). if EvaluateAdversary(B0) returns 1, exit the procedure with value 1 as well. (6) Otherwise, continue with another bin. (7) If we reach this step, no placement of i results in victory of Algorithm.
We return 0 and exit.
Procedure Main: Input is a bin configuration B = (a; b; c; I). (1) Fix parameters S; T . (2) Run EvaluateAdversary(B). (3) If EvaluateAdversary(B) returns 1 (the game is won for player Algorithm), report failure. (4) Otherwise: (5) Print the tree currently in memory, erase the bin configuration cache. (6) For any cached bin configuration C that is linked in the tree, run
Main(C) with a blank cache.
(7) Output the game tree. 3.1
Verifying the Offline Optimum Guarantee When we evaluate a turn of the Adversary, we need to create the list L = f0; 1; : : : ; yg f0; 1; : : : ; T g of items that Adversary can actually send while satifying the Online Bin Stretching guarantee. We employ the following steps:
2. Then, we do a linear search on the interval fU B; U B 1; : : : ; LBg using a procedure Test that checks a single multiset I0, where I0 is I plus the item in question.
Upper and lower bounds. The running time of procedure Test will be cubic in terms of T in the worst case. We therefore reduce the number of calls to Test by creating good lower and upper bounds on the maximal item y which Adversary can send.
To find a good lower bound, we employ a standard bin packing algorithm called Best Fit Decreasing. Best Fit Decreasing packs items from I into three bins of capacity T with items in decreasing order, packing an item into a bin where it “fits best” – where it minimizes the empty space of a bin. Best Fit Decreasing is a linear-time algorithm (it does not need to sort items in I, as the implementation of I stores them in sorted order).
Our desired lower bound LB will be the maximum empty space over all three bins, after Best Fit Decreasing has ended packing. Such an item can always be sent without invalidating the Online Bin Stretching guarantee.
Our upper bound U B is comparatively simpler; for a bin configuration (a; b; c; I), it will be set to min(T; 3T a b c). Clearly, no larger item can be sent without raising the total size of all items above 3T .
Procedure Test. Procedure Test is a sparse modification of the standard dynamic programming algorithm for Knapsack. Given a multiset I; jIj = n on input, our task is to check whether it can be packed into three bins (knapsacks) of capacity T each.
We use a queue-based algorithm that generates a queue Qi of all valid triples (a; b; c) that can arise by packing the first i items.
To generate a queue Qi+1, we traverse the old queue Qi and add the new item I[i + 1] to the first, second and third bin, creating up to three triples that need to be added to Qi+1.
We make sure that we do not add a triple several times during one step, we mark its addition into a auxilliary f0; 1g array F . Note that the queue Qi+1 needs only Qi and the item I[i] for its construction, and so we can save space by switching between queues Q1 and Q2, where Q2i+1 = Q1 and Q2i = Q2.
The time complexity of the procedure Test is O(jIj T 3) in the worst case.
However, when a bin configuration contains large items, the size of the queue is
substantially limited and the actual running time is much better.
Procedure Test:
Input is a multiset of items I.
(1) Create two queues Q1; Q2.
(2) Add the triple (I[
Notes: We employ two small optimizations that were not yet mentioned. First, we sort the numbers (a; b; c) in each triple to ensure a b c, saving a small amount of space and time. Second, we use one global array F in order to avoid initializing it with every call of the procedure Test.
It is also worth noting that we could alternatively implement the procedure
Test using integer linear programming or using a CSP solver (which has been
done in [
Caching Our minimax algorithm employs extensive use of caching. We cache any solved instance of procedure Test as well as any evaluated bin configuration B with its value.
Hash table limitation. We store a large hash table of fixed size, with each entry being a separate chain. With each entry we store the number of accesses. When a chain is to be filled over a fixed limit, we eliminate an entry with the least number of accesses.
To allow hash tables of variable size, our hash function returns a 64-bit number, which we trim to the desired size of our hash table.
In our definition of a bin configuration (a; b; c; I), we do not require the loads a; b; c to be sorted. However, configurations which differ only by a permutation of the values a; b; c are equivalent, and so we sort these numbers when inserting a bin configuration into the hash table.
Hash function. Our hash function is based on Zobrist hashing [
For each bin configuration, we count occurences of items, creating pairs (i; f ) 2 f1; : : : ; T g f0; 1 : : : ; 3T g, where i is the item type and f its frequency. As an example, a bin configuration (3; 2; 3; f1; 1; 1; 1; 2; 3g) forms pairs (1; 4); (2; 1); (3; 1); (4; 0); (5; 0) and so on.
At the start of our program, we associate a 64-bit number with each pair (i; f ). We also associate a 64-bit number for each possible load of bin A, bin B and bin C.
The Zobrist hash function is then simply a XOR of all associated numbers for a particular bin configuration.
The main advantage of this approach is fast computation of new hash values. Suppose that we have a bin configuration B with hash H. After one round of the player Adversary and one round of the player Algorithm, a new bin configuration B0 is formed, with one new item placed. Calculating the hash H0 of B0 can be done in time O(1), provided we remember the hash H – the new hash is calculated by applying XOR to H, the new associated values, and the previous associated values which have changed.
Caching of the procedure Test. So far, we have described cashing of the bin configurations. We also use the same approach for caching the values of the procedure Test. To see the usefulness, note that the procedure Test does not use the entire bin configuration B = (a; b; c; I) as input, but only the multiset I. Therefore, we aim to eliminate overhead that is caused by calling Test on a different bin configuration, but with the same multiset I.
Our hash function and hash table approaches are the same in both cases. 3.3
Tree Pruning Alongside the extensive caching described in Subsection 3.2, we also prune some bin configurations where it is possible to prove that a simple online algorithm is able to finalize the packing. Such a bin configuration is then clearly won for player Algorithm, as it can follow the output of the online algorithm.
Such situations are called good situations and have been introduced in the
paper of Böhm, Sgall, van Stee and Veselý [
Recall that in our game BSG(S; T ), the player Algorithm is trying to pack all three bins with capacity S 1. Therefore, we define S0 = S 1 and use S0 in our definitions.
We restate the good situations for an instance of BSG(S0; T ) for general S0; T
with = S0 T satisfying T =3, while the authors of [
Good Situation 1. [
Good Situation 2. [
Good Situation 3. [
Good Situation 5. [
The notion of bin configuration (Definition 2) as well as most of the minimax algorithm can be straightforwardly generalized for m > 3. When generalizing the algorithm for larger m, one must expect a slowdown, as the complexity of the sparse dynamic programming from Section 3.1 is now O(jIj T m).
One notion that does not generalize very well are the good situations of Section 3.3. For instance, the formula a + b mT in the statement of Good Situation 1 will be much less useful as m grows. Some good situations, like Good Situation 2, have no clear generalization for growing m.
Therefore, we disable the pruning using good situations whenever computing a lower bound for m > 3.
Despite a significant increase in time complexity, we were able to produce results for m = 4 and m = 5. See Table 2 for our results on four and five bins. We include the lower bound along with the implementations, publishing it online at http://iuuk.mff.cuni.cz/ bohm/p/bs/lowerbound-sofsem.zip.
We have implemented a simple independent C++ program which verifies that a given game tree is valid and accurate. While verifying our lower bound manually may be laborious, verifying the correctness of the C++ program should be manageable. The verifier is available along with the rest of the programs and data. 7
We have computed new lower bounds for the problem Online Bin Stretching on 3,4 and 5 bins. A natural next step is to produce a better online algorithm for the case m = 3 and tighten the lower bound/upper bound gap. Still, we are not particularly convinced that 45=33 is the right lower bound for this problem.
We also hope that insight generated from our lower bounds for Online Bin Stretching on a small number of bins may yield a new lower bound for Online Bin Stretching on any number of bins, a long-standing open problem in the area.
We thank Jiří Sgall, Rob van Stee and Pavel Veselý for their suggestions, comments and proofreading.