# A Dense Hierarchy of Sublinear Time Approximation Schemes for Bin Packing - Computer Science > Computational Complexity

A Dense Hierarchy of Sublinear Time Approximation Schemes for Bin Packing - Computer Science > Computational Complexity - Download this document for free, or read online. Document in PDF available to download.

Abstract: The bin packing problem is to find the minimum number of bins of size one topack a list of items with sizes $a 1,

., a n$ in $0,1$. Using uniformsampling, which selects a random element from the input list each time, wedevelop a randomized $O{n\log n\log\log n\over \sum {i=1}^n a i}+{1\over\epsilon}^{O{1\over\epsilon}}$ time $1+\epsilon$-approximation scheme forthe bin packing problem. We show that every randomized algorithm with uniformrandom sampling needs $\Omega{n\over \sum {i=1}^n a i}$ time to give an$1+\epsilon$-approximation. For each function $sn: N ightarrow N$, define$\sumsn$ to be the set of all bin packing problems with the sum of itemsizes equal to $sn$. For a constant $b\in 0,1$, every problem in$\sumn^{b}$ has an $On^{1-b}\log n\log\log n+{1\over\epsilon}^{O{1\over\epsilon}}$ time $1+\epsilon$-approximation for anarbitrary constant $\epsilon$. On the other hand, there is no $on^{1-b}$ time$1+\epsilon$-approximation scheme for the bin packing problems in$\sumn^{b}$ for some constant $\epsilon>0$.

Author: ** Richard Beigel, Bin Fu**

Source: https://arxiv.org/