Gerhard J. Woeginger

We study online bounded space bin packing in the resource

augmentation model of competitive analysis.

In this model, the online bounded space packing algorithm has

to pack a list L of items in (0,1] into a small number of

bins of size b>=1.

Its performance is measured by comparing the ...
more >>>

Richard Beigel, Bin Fu

The bin packing problem is to find the minimum

number of bins of size one to pack a list of items with sizes

$a_1,\ldots , a_n$ in $(0,1]$. Using uniform sampling, which selects

a random element from the input list each time, we develop a

randomized $O({n(\log n)(\log\log n)\over ...
more >>>