2
$\begingroup$

The multiple knapsack problem (MKP) is defined in "A PTAS for the Multiple Knapsack Problem" as:

  • Instance: A pair $(B, S)$ where $B$ is a set of $m$ knapsacks and $S$ is a set of $n$ items. Each bin $j\in B$ has a capacity $c(j)$, and each item has a size $s(i)$ and a profit $p(i)$.
  • Objective: Find a subset $U\subseteq S$ of maximum profit such that $U$ has a feasible packing in $B$.

To prove that there is no FPTAS for MKP, the authors reduce partition problem (PP) to MKP with $m=2$ as follows:

Given an instance of PP, $a_{1},\ldots,a_{2n}$. We set $c(1)=c(2)=\frac{1}{2}\sum_{i=1}^{2n}a_i$. We have $2n$ items, one for each number in the PP: the size of item $i$ is $s(i)=a_i$ and the profit is $p(i)=1$. If the PP has a solution, the profit of an optimum solution to the corresponding MKP is $2n$; otherwise it is at most $2n-1$.

However, I do not understand why the created instance of MKP is hard. I mean we have a set of $2n$ items where each item $i$ has size $s(i)=a_i$ and a profit $p(i)=1$. Also, we have $2$ knapsacks with identical capacity $c(1)=c(2)=\frac{1}{2}\sum_{i=1}^{2n}a_i$. We would like to maximize the number of assigned items to the two knapsacks such that the capacity of each knapsack is respected. Why we could not do the following?

  1. Sort the items in increasing order of their sizes;
  2. Pick an arbitrary knapsack, say $1$;
  3. Fill it with items until its capacity is attained; and
  4. Repeat 2. and 3. for knapsack $2$.

Sure I am missing something here but I do not know where.

$\endgroup$
5
$\begingroup$

There is no guarantee that the packing algorithm you suggested will lead to an optimal packing. Say you have two knapsacks of capacity 5, and objects of size 1, 2, 3 and 4. An optimal packing would be putting 1 and 4 into knapsack 1, and 2 and 3 into the other knapsack (switching the indexes on the knapsacks would also be another alternative solution and this is a further complication). The greedy algorithm you have given would not result in this packing.

$\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.