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
90C27 Combinatorial optimization
90C10 Integer programming
05B40 Combinatorial aspects of packing and covering
90C09 Boolean programming
Full Text: DOI