Probabilistic bounds for dual bin-packing (Q1060845)

The problem called dual bin-packing is: given a set of n piece sizes and a fixed number m of unit capacity bins, pack as many pieces as possible into the bins. The problem is NP-complete; a heuristic is known that achieves 6/7 of the optimal number of pieces in all cases. Here we study the first fit increasing heuristic under the assumption that piece sizes are chosen uniformly from [0,1]. We show that, given a desired degree of confidence 1-\(\epsilon\), if n piece sizes \(\bar X=(X_ 1,...,X_ n)\) are chosen uniformly, then \(P[OPT(\bar X)/FFI(\bar X)<1+O(1/\sqrt{n})]\geq 1-\epsilon\) where \(FFI(\bar X)\) is the number of pieces packed by the heuristic and \(OPT(\bar X)\) is largest number that canbe packed. Thus the performance of the FFI policy can be made arbitrarily close to that of the optimal policy with any desired degree of confidence, for large sample sizes. It is also shown that, at any desired confidence level, \(FFI(\bar X)=\Omega (\sqrt{n})\) and \(FFI(\bar X)=O(\sqrt{n}).\) A lower bound on the expectation of \(FFI(\bar X)\) is derived. The proofs are based upon the distribution of the one-sided Kolmogorov-Smirnov statistic.