Approximation Algorithms for Generalized Multidimensional Knapsack

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 packin...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2021-02
Main Authors: Khan, Arindam, Sharma, Eklavya, Sreenivas, K V N
Format: Article
Language:English
Subjects:
Algorithms
Approximation
Knapsack problem
Mathematical analysis
Operations research
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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+\epsilon)\)-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.
ISSN:2331-8422