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?
- Sort the items in increasing order of their sizes;
- Pick an arbitrary knapsack, say $1$;
- Fill it with items until its capacity is attained; and
- Repeat 2. and 3. for knapsack $2$.
Sure I am missing something here but I do not know where.
