5
$\begingroup$

The generalized assignment problem (GAP) [1] is given by:

  • Instance: A pair $(B,S)$ where $B$ is a set of $m$ bins (knapsacks) and $S$ is a set of $n$ items. Each bin $j∈B$ has a capacity $c(j)$, and for each item $i$ and bin $j$, we are given a size $s(i, j)$ and a profit $p(i, j)$.

  • Objective: Find a subset $U ⊆ S$ that has a feasible packing in $B$ and maximizes the profit of the packing.

In [1], the authors proved that GAP is NP-hard even when:

  • $p(i,j) = 1$ for all items $i$ and bins $j$.
  • $s(i,j)=1$ or $s(i,j)=1+δ$ for all items $i$ and bins $j$.
  • $c(j)=3$ for all bins $j$.

Analyzing this instance, I can see that GAP is NP-hard when $p(i,j)=1$ for all items $i$ and bins $j$ and each bin can pack at most three balls. This observation raises the following question for me.

My question: Is GAP NP-hard when $p(i,j) = 1$ for all items $i$ and bins $j$ and each bin can pack at most two balls?


[1] A Polynomial Time Approximation Scheme for the Multiple Knapsack Problem

$\endgroup$
  • $\begingroup$ How much is $\delta$? $\endgroup$ – Mengfan Ma Nov 7 at 2:32
  • $\begingroup$ I think the authors wanted to say that the sizes are either $1$ or larger than $1$. I think it does not matter much about $\delta$, but probably $0<\delta<1$. $\endgroup$ – Jika Nov 7 at 3:01
2
$\begingroup$

You can reduce numerical 3-dimensional matching (N3DM) to your problem.

Given an instance of N3DM $X\times Y\times Z$ with the bound $b$, say $X=\{x_1,\ldots,x_k\},Y=\{y_1,\ldots,y_k\},Z=\{z_1,\ldots,z_k\}$, you can construct $k$ bins with capacities $b-x_1+M+M^2,\ldots,b-x_k+M+M^2$, and $2k$ balls with sizes $y_1+M,\ldots,y_k+M, z_1+M^2,\ldots,z_k+M^2$, where $M$ is a very large number. Now there is a valid solution to the N3DM instance if and only if you can pack all the $2k$ balls.

$\endgroup$
  • $\begingroup$ Thanks. From N3DM to my problem that's fine. On the other hand, if we pack all $2k$ balls, how do we know that we solved N3DM? I mean maybe a bin packs more than two balls? $\endgroup$ – Jika Nov 8 at 14:30
  • $\begingroup$ @Jika Didn't you say "each bin can pack at most two balls"? $\endgroup$ – xskxzr Nov 8 at 16:03
  • $\begingroup$ @Jika Maybe I misunderstood your question, but it doesn't matter, this construction still works. If a bin packs more than two balls, it must pack more than two $y_i$ balls and zero $z_i$ balls, then another bin would pack more than one $z_i$ balls, which is impossible. $\endgroup$ – xskxzr Nov 8 at 16:18
  • $\begingroup$ Yes, you are right. Each bin packs at most two balls, so my comment did not have much sense. So, if I pack $2k$ balls in my problem then each bin packs 2 balls and they must be one $y_i$ ball and one $z_i$ ball? $\endgroup$ – Jika Nov 8 at 16:37
  • $\begingroup$ Yes, two $z_i$ balls are overweight and zero $z_i$ balls would make another bin overweight. $\endgroup$ – xskxzr Nov 8 at 16:41

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.