zbMATH — the first resource for mathematics

(Probably) the minimum sum of squares. (English) Zbl 0666.90055
The paper analyzes Nielsen’s block packing rule for the ‘minimum sum of squares’ bin packing problem [see T. N. Nielsen, “Combinatorial allocation problems”, Ph. D. Diss., TR 85-29, Dept. Computer Sci., Univ. Arizona, Tucson (1985)]. Let block(x) resp. opt(x) denote the value of the constructed resp. optimal solution for n pieces of size $$x_ i\in [0,\sigma]$$, $$i=1,...,n$$, packed into K bins. Using the two-sided Kolmogorov-Smirnov statistic the distribution of block(x) is studied. Assuming that all piece sizes are uniformly distributed on $$[0,\sigma]$$, and given a desired degree of confidence $$1-\theta$$, it is proved that $P[block(x)/opt(x)\leq 1+0(n^{-0.5})]\geq 1-\theta.$
Reviewer: U.Zimmermann
MSC:
 90C27 Combinatorial optimization 90C10 Integer programming 05B40 Combinatorial aspects of packing and covering 90C09 Boolean programming
Full Text: