Approximation Algorithms for Generalized Multidimensional Knapsack
share
We study a generalization of the knapsack problem with geometric and vector constraints. The input is a set of rectangular items, each with an associated profit and d nonnegative weights (d-dimensional vector), and a square knapsack. The goal is to find a non-overlapping axis-parallel packing of a subset of items into the given knapsack such that the vector constraints are not violated, i.e., the sum of weights of all the packed items in any of the d dimensions does not exceed one. We consider two variants of the problem: (i) the items are not allowed to be rotated, (ii) items can be rotated by 90 degrees. We give a (2+ϵ)-approximation algorithm for this problem (both versions). In the process, we also study a variant of the maximum generalized assignment problem (Max-GAP), called Vector-Max-GAP, and design a PTAS for it.
READ FULL TEXT