Parameterized On-Line Bin Covering
Z Guochuan · Or Transactions · 1999
In this note, we consider the on-line bin covering problem in which all item sizes are not larger than 1/k (k ≥1 is an integer). A tight upper bound is presented and the sample algorithm Next Fit is shown to be the best possible. Our result generalizes the work by Csirik and Totik [3] in 1988. Moreover, we give a nontrivial upper bound for the two dimensional case.