Polytopes, permutations, and the bin packing problems

We consider the NEXT FIT and DUAL NEXT FIT algorithms for the one-dimensional bin and dual bin packing problems. We introduce polytopes derived from these algorithms in such a way that each polytope corresponds to an arrangement of objects into bins produced by one of the bin packing algorithms. In the case of a continuous uniform distribution on object sizes, the volume of this polytope is the probability that the corresponding arrangement occurs.; In the dual bin case, we calculate the expectation and variance for the number of bins used and calculate a (three-variable) generating function for the probability that a given number of objects uses a particular number of bins. We furthermore introduce a map on the unit hypercube that transforms the problem into a question of permutation enumeration. In the process, we generalize the hook decomposition [5] of Gessel and provide a combinatorial explanation of why the generating function for the dual bin case specializes to the generating function for derangements.; We proceed to calculate the continuous and discrete generating functions in the threshold k dual bin packing problem, and generalize the restatement as a question of permutation enumeration, introducing the k-hook decomposition of permutations.; The techniques we have introduced for the dual bin case can be modified for the bin packing problem. We do this and reduce computation of polytope volume to enumeration of permutations according to their numbers of maximal runs or peaks and valleys. As a result, we directly recover the expectation and variance results of Hofri [10, 9] as well as Hofri's generating function for the capacity 1 bin case.; We introduce the notion of a “k”-marked permutation shape in order to generalize the combinatorics for the capacity 1 bin case to the capacity k situation. As a result, we are able to explicitly calculate the capacity 2 generating function.