2010/07/07 by Richard Beigel, Bin Fu, Beigel, Richard +1
Engineering · Computer Science · #Optimization and Packing Problems #Advanced Manufacturing and Logistics Optimization #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.1007.1260
The bin packing problem is to find the minimum number of bins of size one to pack a list of items with sizes a1,..., an 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)(loglog n)\over ∑i=1n ai+(1\over ε)^O(1\overε)) time (1+ε)-approximation scheme for the bin packing problem. We show that every randomized algorithm with uniform random sampling needs Ω(n\over ∑i=1n ai) time to give an (1+ε)-approximation. For each function s(n): N→ N, define ∑(s(n)) to be the set of all bin packing problems with the sum of item sizes equal to s(n). For a constant b∈ (0,1), every problem in ∑(nb) has an O(n1-b(log n)(loglog n)+(1\over ε)^O(1\overε)) time (1+ε)-approximation for an arbitrary constant ε. On the other hand, there is no o(n1-b) time (1+ε)-approximation scheme for the bin packing problems in ∑(nb) for some constant ε>0.