Thursday, October 25, 2012

On line bin packing

I talked for a few minutes about my research on on-line bin packing, in the paper "Markov chains, computer proofs, and average-case analysis of best fit bin packing". This provides an example of a multi-dimensional Markov chain in which we are interested in recurrence/transience properties, but such properties are much harder to pin down than they were for the random walks in $\mathbb{Z}^d$ that we considered in the last lecture.

In this research we consider items, of sizes which are uniformly chosen amongst the integers $1,2,\dotsc,j$, say $j=8$, that arrive in a stream, and as each item arrives it must be packed in a bin. Initially there are an infinite number of empty bins, of some size $k$, say $k=11$. In the Markov chain that models the process of on-line best-fit bin packing the state can be represented as $(x_1,x_2,\dotsc,x_{10})$, where $x_i$ is the number of bins that we have started, but which are not yet full, and which have a gap of $i$. One way to pack the bins is Best Fit. As each iterm arrives we place in a partially full bin that it most nearly completes, or in an empty bin if it fits in no partially full bin. So, for example, in state
$(x_1,x_2,\dotsc,x_{10})=(1,0,3,1,0,0,0,0,0,0)$ an arriving item of size 2 would be placed in the bin with a gap of 3 and take us to state $(2,0,2,1,0,0,0,0,0,0)$. An arrival of size 7 would start a new bin and take us to state $(1,0,3,2,0,0,0,0,0,0)$.

It is interesting to ask if infinitely there is a return to the state $(0,0,\dotsc,0)$ in which there are no partially-full bins present (i.e. if the Markov chain is recurrent). It turns out the the Markov chain with $(j,k)=(8,11)$ is transient, but one with $(j,k)=(8,10)$ is recurrent.

You might like to view these seminar slides for more details. (These were for a faculty colloquium and aimed at a general audience of mathematicians, and so it should be well within your knowledge of mathematics to understand these slides.)

There are applications of this theory to the design algorithms for building packets of Internet data. I also once did a project about on line packing of chicken pieces into supermarket packages of 4 chicken breasts, under the constraint that each package should be at least 500g. The idea is to do this so as to minimizes the average amount by which a pack exceeds 500g.