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.
Complete list of metadatas

Cited literature [14 references]  Display  Hide  Download

https://halshs.archives-ouvertes.fr/halshs-00115660
Contributor : Lucie Label <>
Submitted on : Wednesday, November 22, 2006 - 3:15:04 PM
Last modification on : Monday, February 3, 2020 - 3:40:14 PM
Document(s) archivé(s) le : Tuesday, April 6, 2010 - 11:14:01 PM

File

B06038.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : halshs-00115660, version 1

Citation

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

Share

Metrics

Record views

399

Files downloads

222