Approximation Algorithms for Generalized Multidimensional Knapsack

Arindam Khan, Eklavya Sharma, K. V. N. Sreenivas

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…