0
$\begingroup$

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 ?

$\endgroup$
  • 1
    $\begingroup$ What is the "multiple knapsack" problem ? $\endgroup$ – Suresh Venkat Jun 20 '13 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 Chekuri Jun 20 '13 at 17:46
4
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.