Abstract | ||
---|---|---|
This paper studies the dynamic bin packing problem, in which items arrive and depart at arbitrary time. We want to pack a sequence of unit fractions items (i.e., items with sizes 1/w for some integer w ≥ 1) into unit-size bins such that the maximum number of bins used over all time is minimized. Tight and almost-tight performance bounds are found for the family of any-fit algorithms, including first-fit, best-fit, and worst-fit. We show that the competitive ratio of best-fit and worst-fit is 3, which is tight, and the competitive ratio of first-fit lies between 2.45 and 2.4985. We also show that no on-line algorithm is better than 2.428-competitive. This result improves the lower bound of dynamic bin packing problem even for general items. |
Year | DOI | Venue |
---|---|---|
2008 | 10.1016/j.tcs.2008.09.028 | Theor. Comput. Sci. |
Keywords | Field | DocType |
bin packing,competitive ratio,on-line algorithm,paper study,dynamic bin packing problem,integer w,online algorithms,competitive analysis,almost-tight performance bound,arbitrary time,unit fractions item,maximum number,any-fit algorithm,lower bound,bin packing problem | Integer,Discrete mathematics,Combinatorics,Upper and lower bounds,Unit fraction,Minimum time,Bin packing problem,Mathematics,Competitive analysis | Journal |
Volume | Issue | ISSN |
409 | 3 | Theoretical Computer Science |
ISBN | Citations | PageRank |
3-540-27580-0 | 21 | 0.97 |
References | Authors | |
12 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Joseph Wun-Tat Chan | 1 | 114 | 8.44 |
Tak-Wah Lam | 2 | 1860 | 164.96 |
Prudence W. H. Wong | 3 | 374 | 38.69 |