An algorithm for multi-dimensional bin packing problem and its average case analysis

An algorithm for multi-dimensional bin packing problem and its average case analysis

Lazarev D.O. (ISP RAS, Moscow, Russia; NRI MIPT, Dolgoprudny, Moscow Region, Russia)

Abstract

The authors consider a multidimensional bin packing problem. For solving the problem, an algorithm is proposed and its average-case analysis is carried out. The algorithm incrementally increases the dimension of hyperrectangles packed, and allows efficiently pack into (d+1)-dimensional bins using an algorithm for packing into d-dimensional bins. During the packing process, our objective is to minimize the expected wasted space of used bins. Best previously known results of the upper bound of the number of hyperrectangles packed were improved. The decrease of expected wasted space is confirmed by computational experiments. The likely problem of average-case analysis is overfitting. It is due to the fact that the minimal expected wasted space is studied for only one distribution or family of distributions of input parameters of the algorithm. In order to deal with overfitting, the proposed algorithm was generalized to the case of any given in advance distribution of rectangles’ sides sizes. The efficiency of the generalized algorithm is confirmed by computational experiments.

Keywords

bin packing; multidimensional bin packing; average case analysis; overfitting; dimension increment algorithm.

Edition

Proceedings of the Institute for System Programming, vol. 38, issue 2, 2026, pp. 35-52

ISSN 2220-6426 (Online), ISSN 2079-8156 (Print).

DOI: 10.15514/ISPRAS-2026-38(2)-3

For citation

Lazarev D.O. An algorithm for multi-dimensional bin packing problem and its average case analysis. Proceedings of the Institute for System Programming, vol. 38, issue 2, 2026, pp. 35-52 DOI: 10.15514/ISPRAS-2026-38(2)-3.

Full text of the paper in pdf (in Russian) Back to the contents of the volume