<p>In a multiple knapsack problem you pack a set of items into several (one-dimensional) knapsacks, whereas in the multidimentional knapsack problem you pack d-dimensional items into one d-dimensional knapsack. The multiple knapsack problem $\max\{\sum_i p_i x_i \mid \sum_i w_{ij}x_i \leq d_j, j=1,2,\ldots,m\}$ is a general 0-1 integer program restricted to positive coefficients. Its integrality gap is unbounded, since it includes the maximum independent set problem whose formulation $\max\{\sum_{v\in V} x_v\mid x_u+x_v\leq 1, \{u,v\}\in E\}$ on an undirected graph $G=(V,E)$ has integrality gap $|V|/2$.</p>

<p>You can find more information on these problems in chapters 9 and 10 of  <a href="http://rads.stackoverflow.com/amzn/click/3540402861" rel="nofollow noreferrer">Kellerer, Pferschy, and Pisinger, "Knapsack problems"</a>.</p>

CC BY-SA 3.0
2013-06-20T17:16:49.733Z
2016-12-09T21:29:51.690Z
2016-12-09T21:29:51.690Z
Marcus Ritt
<p>What is the difference between Multiple Knapsack problem and Multidimensional Knapsack Problem? (<a href="http://en.wikipedia.org/wiki/List_of_knapsack_problems#Multiple_constraints" rel="nofollow">http://en.wikipedia.org/wiki/List_of_knapsack_problems#Multiple_constraints</a>) According to the literature, Multiple Knapsack problem has integrality gap of 2, what is the integrality gap for Multidimensional Knapsack Problem ?</p>

CC BY-SA 3.0
2013-06-20T14:38:38.877Z
What is the "multiple knapsack" problem ?
Suresh Venkat
CC BY-SA 3.0
2013-06-20T17:46:30.790Z
The definitions of the problems can be found in various sources and are easy to understand. The integrality gap question is not well formed because it depends on the specific LP relaxation you have in mind. It would help to edit the question to make clear what you want to know. Multi-dimensional knapsack is also the same as packing integer programs (PIPs) and there are several papers that you can easily find by a Google search.
Chandra Chekuri
<approximation-algorithms><linear-programming><integer-programming><integrality-gap>
Difference between Multiple Knapsack problem and Multidimensional Knapsack Problem
Vivek Bagaria
# Difference between Multiple Knapsack problem and Multidimensional Knapsack Problem

(Asked by: username_0 on 2013-06-20)

What is the difference between Multiple Knapsack problem and Multidimensional Knapsack Problem? (<http://en.wikipedia.org/wiki/List_of_knapsack_problems#Multiple_constraints>) According to the literature, Multiple Knapsack problem has integrality gap of 2, what is the integrality gap for Multidimensional Knapsack Problem ?

**Tags:** approximation-algorithms, linear-programming, integer-programming, integrality-gap
> **Comments:**
> **username_1**: What is the "multiple knapsack" problem ?  
> **username_2**: The definitions of the problems can be found in various sources and are easy to understand. The integrality gap question is not well formed because it depends on the specific LP relaxation you have in mind. It would help to edit the question to make clear what you want to know. Multi-dimensional knapsack is also the same as packing integer programs (PIPs) and there are several papers that you can easily find by a Google search.  

---

## 1 answers

### Answer by username_3 on 2013-06-20. Score: 4

In a multiple knapsack problem you pack a set of items into several (one-dimensional) knapsacks, whereas in the multidimentional knapsack problem you pack d-dimensional items into one d-dimensional knapsack. The multiple knapsack problem $\max\{\sum\_i p\_i x\_i \mid \sum\_i w\_{ij}x\_i \leq d\_j, j=1,2,\ldots,m\}$ is a general 0-1 integer program restricted to positive coefficients. Its integrality gap is unbounded, since it includes the maximum independent set problem whose formulation $\max\{\sum\_{v\in V} x\_v\mid x\_u+x\_v\leq 1, \{u,v\}\in E\}$ on an undirected graph $G=(V,E)$ has integrality gap $|V|/2$.

You can find more information on these problems in chapters 9 and 10 of [Kellerer, Pferschy, and Pisinger, "Knapsack problems"](http://rads.stackoverflow.com/amzn/click/3540402861).


---

