@inproceedings{9a306d9986c841b3892847e6ee3372d9,
title = "On Dynamic Bin Packing: An Improved Lower Bound and Resource Augmentation Analysis",
abstract = "We study the dynamic bin packing problem introduced by Coffman, Garey and Johnson [7]. This problem is a generalization of the bin packing problem in which items may arrive and depart from the packing dynamically. The main result in this paper is a lower bound of 2.5 on the achievable competitive ratio, improving the best known 2.428 lower bound [3], and revealing that packing items of restricted form like unit fractions (i.e., of size 1/k for some integer k), which can guarantee a competitive ratio 2.4985 [3], is indeed easier.We also investigate the resource augmentation analysis on the problem where the on-line algorithm can use bins of size b (> 1) times that of the optimal off-line algorithm. An interesting result is that we prove b = 2 is both necessary and sufficient for the on-line algorithm to match the performance of the optimal off-line algorithm, i.e., achieve 1-competitiveness. Further analysis is made to give a trade-off between the bin size multiplier b and the achievable competitive ratio.",
keywords = "Competitive Ratio, Item Size, Resource Augmentation, Harmonic Algorithm, Average Case Behavior",
author = "Chan, \{Wun Tat\} and Wong, \{Prudence W.H.\} and Yung, \{Fencol C.C.\}",
note = "* This research is partly supported by Hong Kong RGC Grant HKU5172/03E. ** This research is partly supported by Nuffield Foundation Grant NAL/01004/G. Publisher copyright: {\textcopyright} 2006 Springer-Verlag Berlin Heidelberg; 12th Annual International Conference on Computing and Combinatorics, COCOON 2006 ; Conference date: 15-08-2006 Through 18-08-2006",
year = "2006",
month = jul,
day = "31",
doi = "10.1007/11809678\_33",
language = "English",
isbn = "3540369252",
series = "Lecture Notes in Computer Science",
publisher = "Springer Berlin Heidelberg",
pages = "309--319",
editor = "Chen, \{Danny Z.\} and Lee, \{D. T.\}",
booktitle = "Computing and Combinatorics",
edition = "1st",
}