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 r(ℬ), and we prove that no on-line algorithm can perform better in the worst case. The value r(ℬ), mainly depends on the largest gap between consecutive bin sizes.
