Is the Generalized Assignment Problem with weights=1 NP-hard?

Question

Description

The Generalized Assignment Problem consists into assigning an items $i$ to a bins $j$.

If we assign item $i$ to bin $j$ (i.e., $x_{ij}=1$) we obtain a profit $p_{ij}$.

Each bin $i$ has its budget $t_i$, and assigning item $i$ to bin $j$ incurs into a cost/weight $w_{ij}$.

The goal is to maximize the overall profit without exhausting the bins' budget: \begin{align} \text{maximize } & \sum_{i=1}^m\sum_{j=1}^n p_{ij} x_{ij}. \\ \text{subject to } & \sum_{j=1}^n w_{ij} x_{ij} \le t_i & & i=1, \ldots, m; \\ & \sum_{i=1}^m x_{ij} = 1 & & j=1, \ldots, n; \\ & x_{ij} \in \{0,1\} & & i=1, \ldots, m, \quad j=1, \ldots, n; \end{align}

Question

This problem is known to be NP-hard.

Is it still NP-hard if the cost/weight is constant, e.g., $w_{ij}=1,\ \forall i,j$?

Answer 1

With $w_{ij}=1$, the problem reduces to a transportation problem, which has several polynomial-time algorithms.