This paper gives probabilistic analyses of two kinds of multidimensional bin packing problems: vector packing and rectangle packing. In the vector packing problem each of the d dimensions can be interpreted as a resource. A given object i consumes aijunits of the jthresource, and the objects packed in any given bin may not collectively consume more than one unit of any resource. Subject to this constraint, the objects are to be packed into a minimum number of bins. The rectangle packing problem is more geometric in character. The ithobject is a d-dimensional box whose jthside is of length aij, and the goal is to pack the objects into a minimum number of cubical boxes of side 1. We study these problems on the assumption that the aijare drawn independently from the uniform distribution over [0,1]. We study a vector packing heuristic called VPACK that tries to place two objects in each bin and a rectangle packing heuristic called RPACK that tries to pack one object into each of the 2d corners of each bin. We show that each of these heuristics tends to produce packings in which very little of the capacity of the bins is wasted. In the case of rectangle packing, we show that the results can be extended to a wide class of distributions of the piece sizes.
A probabilistic analysis of multidimensional bin packing problems / Karp, R. M.; Luby, M.; Marchetti-Spaccamela, A.. - (1984), pp. 289-298. (Intervento presentato al convegno 16th Annual ACM Symposium on Theory of Computing, STOC 1984 tenutosi a Washington; United States) [10.1145/800057.808693].
A probabilistic analysis of multidimensional bin packing problems
Marchetti-Spaccamela A.
1984
Abstract
This paper gives probabilistic analyses of two kinds of multidimensional bin packing problems: vector packing and rectangle packing. In the vector packing problem each of the d dimensions can be interpreted as a resource. A given object i consumes aijunits of the jthresource, and the objects packed in any given bin may not collectively consume more than one unit of any resource. Subject to this constraint, the objects are to be packed into a minimum number of bins. The rectangle packing problem is more geometric in character. The ithobject is a d-dimensional box whose jthside is of length aij, and the goal is to pack the objects into a minimum number of cubical boxes of side 1. We study these problems on the assumption that the aijare drawn independently from the uniform distribution over [0,1]. We study a vector packing heuristic called VPACK that tries to place two objects in each bin and a rectangle packing heuristic called RPACK that tries to pack one object into each of the 2d corners of each bin. We show that each of these heuristics tends to produce packings in which very little of the capacity of the bins is wasted. In the case of rectangle packing, we show that the results can be extended to a wide class of distributions of the piece sizes.File | Dimensione | Formato | |
---|---|---|---|
Karp_A-probabilistic_1984.pdf
solo gestori archivio
Tipologia:
Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza:
Tutti i diritti riservati (All rights reserved)
Dimensione
893.6 kB
Formato
Adobe PDF
|
893.6 kB | Adobe PDF | Contatta l'autore |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.