Abstract

The original knapsack problem is well known to be NP-complete. In a multidimensional version, one have to decide whether a $p\in {\mathbb{N}}^k$ is in the sumset-sum of a set $X\subseteq {\mathbb{N}}^k$. In this paper, we are going to investigate a communication complexity problem related to this. We are also going to prove some results about the special case of the multidimensional knapsack problem, when the set $X$ is in the form $X=A_1\times \cdots \times A_k\subseteq {\mathbb{N}}^k$, where $A_i$ is a so-called regular set for every $i=1,2,\dots ,k$.

Keywords

Mathematical Subject Classification

Milestones

Authors