Approximating the orthogonal knapsack problem for hypercubes

Abstract. Given a list of d-dimensional cuboid items with associated profits, the orthogonal knapsack problem asks for a packing of a se-lection with maximal profit into the unit cube. We restrict the items + ɛ)-approximation for the two-to hypercube shapes and derive a ( 5 4 dimensional case. In a second step we generalize our result to a ( 2d +1 2 d +ɛ)approximation for d-dimensional packing.