Summary
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; an 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-ε, if n piece sizes ¯X = (X 1,..., Xn) are chosen uniformly, then
where FFI(¯X) is the number of pieces packed by the heuristic and OPT(¯X) is largest number that can be 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(¯X)=Ω(√n) and FFI(¯X) = O(√n). A lower bound on the expectation of FFI(¯X) is derived. The proofs are based upon the distribution of the one-sided Kolmogorov-Smirnov statistic.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Birnbaum, Z.W., Tingey, F.H.: One-sided confidence contours for probability distribution functions. Ann. Math. Stat. 22, 592–596 (1951)
Bruno, J.L., Downey, P.J.: Probabilistic bounds on the performance of list scheduling. SIAM J. Comput. 15, No. 2 (May 1986)
Coffman, E.G., Jr, Leung, J. Y.-T., Ting, D.W.: Bin packing: Maximizing the number of pieces packed. Acta Inf. 9, 263–271 (1978)
Coffman, E.G., Jr, Leung, J.Y.-T.: Combinatorial analysis of an efficient algorithm for processor and storage allocation. SIAM J. Comput. 8, 202–217 (1979)
Coffman, E.G., Jr, Garey, M.R., Johnson, D.S.: Approximation algorithms for bin-packing-an updated survey. In: Algorithm design for computer system design (G. Ausiello M. Lucertini, P. Serafini, eds.), pp. 49–106. New York: Springer 1984
Coffman, E.G., Jr, Gilbert, E.N.: On the expected relative performance of list scheduling. Oper. Res. 33, (3) 548–561 (May–June 1985)
Downey, P.: Bounds on prefix algorithms for dual bin-packing. TR 85-5, Dep. Comput. Sci., University of Arizona, Tucson, AZ, 1985
Durbin, J.: Distribution theory for tests based on the sample distribution function. Philadelphia: SIAM 1973
Dvoretzky, A., Kiefer, J., Wolfowitz, J.: Asymptotic minimax character of the sample distribution function and of the classical multinomial estimator. Ann. Math. Stat. 27, 642–669 (1956)
Garey, M.R., Johnson, D.S.: Computers and intractibility: A guide to the theory of NP-completeness. San Francisco: Freeman 1979
Knödel, W.: A bin packing algorithm with complexity O(n log n) and performance 1 in the stochastic limit. Proc. 10th Symp. Math. Found. Comput. Sci., Lect. Notes Comput. Sci. 118, 369–377 (1981)
Leung, J.Y.: Fast algorithms for packing problems. Dissertation, Computer Science Dept., Pennsylvania State University, University Park, PA, USA, 1977
Miller, L.H.: Table of percentage points of Kolmogorov statistics. J. Am. Stat. Assoc. 51, 111–121 (1956)
Smirnov, N.V.: Approximate laws of distribution of random variables from empirical data. Usp. Mat. Nauk 10, 179–206 (1941)
Author information
Authors and Affiliations
Additional information
The work of the first author was partially supported by NSF Grant MCS80-04257; the work of the second author was partially supported by NSF Grant MCS80-04679
Rights and permissions
About this article
Cite this article
Bruno, J.L., Downey, P.J. Probabilistic bounds for dual bin-packing. Acta Informatica 22, 333–345 (1985). https://doi.org/10.1007/BF00265685
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF00265685