Optimal on-line algorithms for variable-sized bin covering

We deal with the variable-sized bin covering problem: Given a list L of items in (0,1] and a finite collection of feasible bin sizes, the goal is to select a set of bins with sizes in and to cover them with the items in L such that the total size of the covered bins is maximized. In the on-line version of this problem, the items must be assigned to bins one by one without previewing future items. This note presents a complete solution to the on-line problem: For every collection of bin sizes, we give an on-line approximation algorithm with a worst-case ratio , and we prove that no on-line algorithm can perform better in the worst case. The value mainly depends on the largest gap between consecutive bin sizes.