<p>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. </p>

<p><a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.226.3387&amp;rep=rep1&amp;type=pdf" rel="nofollow noreferrer">UGAP is NP-hard</a>. The greedy algorithm <strong>ALG</strong> 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 <strong>ALG</strong> 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 <strong>ALG</strong> attains the bound of $1-(1-1/k)^k$.</p>

<p><a href="https://pdfs.semanticscholar.org/9546/492e6da16d2baba7891514d9f045150a127a.pdf" rel="nofollow noreferrer">This paper</a> 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 <strong>weighted</strong> generalized assignment problem. What about the UGAP?</p>

CC BY-SA 3.0
2018-04-08T20:26:20.953Z
Would you mind clarifying the difference between the weighted and unweighted problem?
Yonatan N
CC BY-SA 3.0
2018-04-08T21:02:20.770Z
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.
Jika
<approximation-algorithms><packing>
Can we find a generic tight example for the greedy algorithm of the unweighted generalized assignment problem?
Jika
# Can we find a generic tight example for the greedy algorithm of the unweighted generalized assignment problem?

(Asked by: username_0 on 2018-04-04)

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](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.226.3387&rep=rep1&type=pdf). 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](https://pdfs.semanticscholar.org/9546/492e6da16d2baba7891514d9f045150a127a.pdf) 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?

**Tags:** approximation-algorithms, packing

> **Comments:**
> **username_1**: Would you mind clarifying the difference between the weighted and unweighted problem?  
> **username_0**: 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.  

---

## 0 answers

