Online algorithms for a dual version of bin packing (Q1112608): Difference between revisions

Suppose a list \(L=(a_ 1,a_ 2,...,a_ n)\) of positive real numbers is given and that \(C\geq \max a_ i\). The dual bin packing problem consists of packing the elements of L into a maximum number of bins so that the sum of the numbers in every bin is at least C. For an online algorithm the elements of L are presented one at a time and must be packed immediately. It is shown that no online algorithm can have a performance ratio better than 1/2. This ratio can be achieved, as is shown by \textit{S. F. Assmann}, \textit{D. S. Johnson}, \textit{D. J. Kleitman} and \textit{J. Y.-T. Leung} [J. Algorithms 5, 502-525 (1984; Zbl 0556.68011)]. Furthermore an online algorithm is given which is asymptotically optimal in case the list L consists of n independent random variables which are all uniformly distributed on (0,1).