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 ?
$\begingroup$
$\endgroup$
2
asked Jun 20, 2013 at 7:21
-
1$\begingroup$ What is the "multiple knapsack" problem ? $\endgroup$– Suresh VenkatJun 20, 2013 at 14:38
-
2$\begingroup$ 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. $\endgroup$– Chandra ChekuriJun 20, 2013 at 17:46
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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".
