Is the generalized assignment problem with un-capacitated agents NP-hard?

Question

I am working on a generalized assignment problem which I typed below. I know it is shown to be NP-hard. I am wondering whether the problem is still NP-hard when the capacity of the agents are assumed to be infinity. In other words, If $b_{ij} = \infty \; \forall i,j$, is the problem still NP-hard? Could anyone help me prove if it is or not?

$min \; \sum_{i,j} c_{ij}x_{ij} $

s.t $\sum_i x_{ij} =1 $

$\sum_j a_{ij}x_{ij} \leq b_{ij} $

$x_{ij} \in \{0,1\}$

Thanks in advance

Answer 1

No. The constraint $\sum_j a_{i,j} x_{i,j} \le \infty$ can be removed. The remaining problem can be solved by picking the smallest element in each column $j$ of $c_{i,j}$. That can be done in one pass over the data $c_{i,j}$. This sounds rather obvious, so what am I missing?