Why this greedy algorithm does not return the optimal solution to this NP-hard problem?

Question

Problem: In the generalized assignment problem with unit-value items, there are $m$ bins of capacity $C$ each. There are $n$ items where each item $i$ has weight $w_{ij}$ with bin $j$. The objective is to assign the items to the bins (while respecting the bins capacities) such that the number of assigned items is maximum. I know that this problem is NP-hard.

Question: why the following algorithm is not optimal?

Algorithm:

• For each bin $j$, assign the maximum. Here, assign the maximum means to iterate the items such that $w_{1j}\leq w_{2j}\leq\cdots\leq w_{nj}$ and add to bin $j$ the items in that order until the capacity $C$ is filled.
• Take the union. This means that, if bin $j$ is assigned a set $S_j$ of items, then the result would be: $\bigcup_j S_j$.

So for example if I have this instance: $C=4$ and $m=3$ and $n=7$. The weights are given by: $$\begin{pmatrix} 2 & 4 & 4\\ 2 & 1 & 4\\ 4 & 1 & 2\\ 4 & 1 & 4\\ 4 & 1 & 4\\ 4 & 4 & 4\\ 4 & 4 & 2 \end{pmatrix}.$$

So the algorithm gives the following assignment:

• bin 1: items 1 & 2,
• bin 2: items 2, 3, 4, & 5
• bin 3: items 3 & 7

Finally, we choose the following assignment:

• bin 1: items 1 & 2,
• bin 2: items 3, 4, & 5
• bin 3: item 7

Maybe I choose the bad example, can you show me how this algorithm fails?

Answer 1

One thing (which has been pointed out in the comments) is that it is unclear what you mean when you say "union". It appears that what you're doing is simply excluding items assigned to previous bins (but perhaps I do not understand, because "union" is a strange word for this). For example, when you've assigned 1,2 to bin 1 and 2,3,4,5 to bin 2, in the first step, in the final output you only assign object 2 to bin 1, and not bin 2.

Under this assumption, here is a simple example that shows that your greedy algorithm is not optimal. Assume we have two bins, both with capacity 5. Assume we have four items, with weights w_1 = 1, w_2 = 2, w_3 = 3, w_4 = 4 (we'll assume each item has the same weight for both bins). Then if you start assigning from smallest weight upwards until the bins are filled, your assignment is:

• bin 1: items 1 and 2
• bin 2: items 1 and 2

and after you exclude previously assigned items you end up placing items 1 and 2 in bin 1 and nothing in bin 2 (which is clearly not optimal, since you can place either of the other items in bin 2).

Perhaps you mean a different greedy algorithm, where first you assign 1 and 2 to bin 1, and then (since 1 and 2) are already assigned, you skip those and start again from lightest to heaviest weight, assigning item 3 to bin 2 (upon which there is no space for item 4). This assigns items 1, 2, and 3, and gets a score of 3.

But of course, it is possible to assign all the items, by assigning 1 and 4 to bin 1, and 2 and 3 to bin 2. The greedy algorithms miss this assignment.

As you've mentioned, this problem is NP-hard; in fact, it is hard even for the version where there are only two bins and the item weights are the same for all bins, where it reduces to the Subset Sum problem.

Answer 2

Let C be even. Take C items where $w_{ij} = 1$ and C items where $w_{ij} = 2$.

Your greedy algorithm will put the same C items in each bin, so you find a solution with C items. Instead you can put C items of size 1 into bin 1, then C/2 items each of size 2 into bin 2 and bin 3, giving a solution where you get C items instead of 2C.