Skip to Main content Skip to Navigation
Other publications

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

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.
Document type :
Other publications
Complete list of metadata

Cited literature [14 references]  Display  Hide  Download
Contributor : Lucie Label <>
Submitted on : Wednesday, November 22, 2006 - 3:15:04 PM
Last modification on : Tuesday, January 19, 2021 - 11:08:27 AM
Long-term archiving on: : Tuesday, April 6, 2010 - 11:14:01 PM


Files produced by the author(s)


  • HAL Id : halshs-00115660, version 1


Bernard Kouakou, Marc Demange, Eric Soutif. On-line bin-packing problem: maximizing the number of unused bins. 2005. ⟨halshs-00115660⟩



Record views


Files downloads