Approximation algorithms for orthogonal packing problems for hypercubes

Orthogonal packing problems are natural multidimensional generalizations of the classical bin packing problem and knapsack problem and occur in many differ-ent 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 or-thogonal 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. We mainly focus on orthogonal knapsack packing restricted to hypercubes and our main results are a (5/4 + )-approximation algorithm for two-dimensional hy-percube knapsack packing, also known as square packing, and a (1+1/2d+)-approximation algorithm for d-dimensional hypercube knapsack packing. In addition we consider d-dimensional hypercube strip packing in the case of a bounded ratio between the shortest and longest side of the basis of the strip. We derive an asymptotic polynomial time approximation scheme (APTAS) for this prob-lem. Finally, we present an algorithm that packs hypercubes with a total profit of at least (1 − )OPT into a large bin (the size of the bin depends on ). This problem is known as hypercube knapsack packing with large resources. A prelim-inary version was published in [15] but especially for the latter two approximation schemes no details were given due to page limitations