On-line bin-packing problem : maximizing the number of unused bins

URL des Cahiers : http://mse.univ-paris1.fr/MSEFramCahier2006.htmCahiers de la Maison des Sciences Economiques 2006.38 - ISSN 1624-0340In this paper, we study the on-line version of the bin-packing problem. We analyze the approximation behavior of an on-line bin-packing algorithm under an approximation criterion called differential ratio. We are interested in two types of results : the differential competitivity ratio guaranteed by the on-line algorithm and hardness results that account for the difficulty of the problem and for the quality of the algorithm developed to solve it. In its off-line version, the bin-packing problem, BP, is better approximated in differential framework than in standard one. Our objective is to determine if or not such result exists for the on-line version of BP.Nous étudions la version on-line du problème bin-packing dans le cadre de l'approximation différentielle. Dans sa version off-line, le problème du bin-packing BP, est mieux résolu en approximation différentielle qu'en approximation classique. Notre objectif est d'établir si ce résultat reste valable dans le cadre on-line. Nous analyserons donc le comportement des algorithmes on-line résolvant le problème BP et déterminons des rapports différentiels compétitifs (résultats positifs) et des résultats négatifs. Ces derniers résultats rendent compte aussi bien de la difficulté du problème que de la qualité des algorithmes élaborés pour les résoudre