1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Several things aren't clear. (1) What does "assign the maximum" mean in "For each bin $j$, assign the maximum"? (2) You talk about then "taking the union", but in your example the set of items assigned to each bin stays the same or shrinks during this step -- how does a union operation shrink a set? $\endgroup$ – j_random_hacker Jul 2 '18 at 15:04
  • $\begingroup$ Try implementing it and running it on many randomly chosen test cases. If it is indeed incorrect, you should be able to find a counterexample. See cs.stackexchange.com/q/59964/755. $\endgroup$ – D.W. Jul 2 '18 at 16:24
  • $\begingroup$ @j_random_hacker I explained more the algorithm. $\endgroup$ – zdm Jul 2 '18 at 16:39
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Very clear. Thanks for your good answer! $\endgroup$ – zdm Jul 2 '18 at 17:27

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.