Abstract
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.
Original language | English |
---|---|
Pages (from-to) | 47-50 |
Number of pages | 4 |
Journal | Operations Research Letters |
Volume | 25 |
Issue number | 1 |
DOIs | |
Publication status | Published - 1999 |