A Dense Hierarchy of Sublinear Time Approximation Schemes for Bin Packing

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,...,a_n$ in $(0,1]$. Using uniform sampling, which selects a rand…