A dense hierarchy of sublinear time approximation schemes for bin packing

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 random element from the input list each time, we develop a randomized (Formula Presented) time (1 + ε)- approximation scheme for the bin packing problem. We show that every randomized algorithm with uniform random sampling needs (Formula Presented) time to...
This data repository is not currently reporting usage information. For information on how your repository can submit usage information, please see our documentation.