Permutation Shapes and the Bin Packing Problem

Marguerite A. Eisenstein-Taylor

To appear at Formal Power Series and Algebraic Combinatorics (FPSAC01), Tempe, Arizona (USA), May 20-24, 2001


Abstract

We define a partition of the unit hypercube into polytopes. These polytopes correspond to arrangements of a sequence of objects into bins in the {next fit} solution to the one-dimensional bin packing problem. The probability that an arrangement appears is given by the volume of the corresponding polytope in the partition. We show that this volume can be calculated as the solution to a problem of permutation enumeration and apply this technique to analyze the behavior of the {next fit} algorithm. R\'{e}sum\'{e}. Nous d\'{e}crivons une partition du hypercube de l'unit\'{e} en polytopes. Ces polytopes correspondent aux arrangements d'une s\'{e}quence d'objets en huches selon la solution de l'algorithme ``next fit" au probl\`{e}me 1-dimensionel de l'emballage des huches. La probabilit\'{e} qu'un arrangement appara\^{\i}t est le volume du polytope correspondant dans la partition. Nous montrons qu'on peut calculer ce volume comme solution d'un probl\`{e}me de l'\'{e}numeration des permutations, et appliquons cette technique afin d'analyser le comportement de l'algorithme ``next fit".


Server START Conference Manager
Update Time 27 Jan 2001 at 12:22:07
Maintainer maylis@labri.u-bordeaux.fr.
Start Conference Manager
Conference Systems