On-line bin-packing problem : maximizing the number of unused binsReport as inadecuate

On-line bin-packing problem : maximizing the number of unused bins - Download this document for free, or read online. Document in PDF available to download.

1 CES - Centre d-économie de la Sorbonne 2 ESSEC Business School 3 CEDRIC - Centre d-Etude et De Recherche en Informatique du Cnam

Abstract : In 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.

Résumé : 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.

Keywords : competitivity ratio On-line algorithm bin-packing problem competitivity ratio.

Author: Bernard Kouakou - Marc Demange - Eric Soutif -

Source: https://hal.archives-ouvertes.fr/


Related documents