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

Bernard Kouakou (), Marc Demange () and Eric Soutif ()
Additional contact information
Bernard Kouakou: CES - Centre d'économie de la Sorbonne - UP1 - Université Paris 1 Panthéon-Sorbonne - CNRS - Centre National de la Recherche Scientifique
Marc Demange: ESSEC Business School
Eric Soutif: CES - Centre d'économie de la Sorbonne - UP1 - Université Paris 1 Panthéon-Sorbonne - CNRS - Centre National de la Recherche Scientifique, CEDRIC - Centre d'études et de recherche en informatique et communications - ENSIIE - Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise - CNAM - Conservatoire National des Arts et Métiers [CNAM]

Université Paris1 Panthéon-Sorbonne (Post-Print and Working Papers) from HAL

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.

Keywords: bin-packing problem; On-line algorithm; competitivity ratio (search for similar items in EconPapers)
Date: 2005-12
Note: View the original document on HAL open archive server: https://shs.hal.science/halshs-00115660
References: View complete reference list from CitEc
Citations:

Published in 2005

Downloads: (external link)
https://shs.hal.science/halshs-00115660/document (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hal:cesptp:halshs-00115660

Access Statistics for this paper

More papers in Université Paris1 Panthéon-Sorbonne (Post-Print and Working Papers) from HAL
Bibliographic data for series maintained by CCSD ().