Approximation algorithms for orthogonal packing problems for hypercubes |
| |
Authors: | Rolf Harren |
| |
Affiliation: | Max-Planck-Institut für Informatik, Campus E 1 4, 66123 Saarbrücken, Germany |
| |
Abstract: | Orthogonal packing problems are natural multidimensional generalizations of the classical bin packing problem and knapsack problem and occur in many different settings. The input consists of a set I={r1,…,rn} of d-dimensional rectangular items ri=(ai,1,…,ai,d) and a space Q. The task is to pack the items in an orthogonal and non-overlapping manner without using rotations into the given space. In the strip packing setting the space Q is given by a strip of bounded basis and unlimited height. The objective is to pack all items into a strip of minimal height. In the knapsack packing setting the given space Q is a single, usually unit sized bin and the items have associated profits pi. The goal is to maximize the profit of a selection of items that can be packed into the bin. |
| |
Keywords: | Orthogonal Knapsack problem Square packing Hypercube packing |
本文献已被 ScienceDirect 等数据库收录! |
|