3
$\begingroup$

In the unweighted generalized assignment problem (UGAP) we have $n$ items and $k$ knapsacks. For each item $i$ and knapsack $j$, there is a weight $w_{ij}$. Also, every knapsack has a capacity $W$. The question of UGAP is to pack the items into the knapsacks such that the weights of the items in any knapsack do not exceed $W$ and the number of all items packed is maximum.

UGAP is NP-hard. The greedy algorithm ALG that maximizes the number of items packed in each knapsack is $1-(1-1/k)^k$-approximation. I am trying to find a tight example for ALG that achieves this bound of $1-(1-1/k)^k$. I can find an example with fixed $n$ and $k$, e.g., $n=4$ and $k=2$ but I would like a generic example of arbitrary $n$ and $k$ such that ALG attains the bound of $1-(1-1/k)^k$.

This paper gives a tight example for the maximum coverage problem, which I think (if I am not mistaken) can be used to construct a tight example for the weighted generalized assignment problem. What about the UGAP?

$\endgroup$
  • $\begingroup$ Would you mind clarifying the difference between the weighted and unweighted problem? $\endgroup$ – Yonatan N Apr 8 '18 at 20:26
  • $\begingroup$ In the unweighted problem, we maximize the number of items packed into the knapsacks subject to the capacity of each knapsack, whereas in the weighted problem, we maximize the weights of items packed into the knapsacks subject to the capacity of each knapsack. $\endgroup$ – Jika Apr 8 '18 at 21:02

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.