Is this problem about picking optimal entries of a matrix NP-complete? I am trying to solve a real-world problem that I was able to reduce to the problem described below. I would like to know the following things:


Is there literature about this problem?
Is the corresponding decision problem NP-complete?
Do you know an efficient algorithm to solve the problem?
If not, what would be a good technique to solve it approximately?


The problem is as follows. Given a $n \times m$ matrix $M$ with entries in $[0, 1]$, and a function $a \colon \{1, \ldots m\} \to \mathbb{N}$. For each column $j$, we want to pick $a(j)$ entries in that column, such that in each row, at most one element was picked. We want to do this in such a way that the sum of the picked values is maximized.

More formally, find a function $T\colon \{1, \ldots n\} \to \{1, \ldots m\} \cup \{\bot\}$ which maps each row to a column (or $\bot$), with the following two properties:


$\forall j \in \{1, \ldots m\} \colon \lvert T^{-1}(j)\rvert = a(j)$
The following expression is maximized: $$
 \sum_{\substack{i=1 \\ T(i) \neq \bot}}^n M_{i, T(i)}
$$


Of course, you could also define it the other way around, with each column mapping to a set of rows. Finally, the corresponding decision problem is in NP, as the function $T$ acts as a certificate.
I tried a reduction to knapsack, as the two seem quite similar, but I was unsuccessful.
Reduce to maximum-weight bipartite matching.

If you just wanted ​ for each j, pick at most a($\hspace{.015 in}$j) entries from the j-th column ,

then the reduction would be

One of the parts is ​ ​ ​ one vertex for each row.

The other part is ​ ​ ​ for each j, a($\hspace{.015 in}$j) vertices for the j-th column .

The weight of each edge is the corresponding matrix entry.

and the reasoning would be

The ​ one vertex per row ​ ensures that at most one element will be picked for each row.

The ​ a($\hspace{.015 in}$j) vertices for the j-th column ​ allows the j-th column to be

used a($\hspace{.015 in}$j) times but prevents it from being used more than that.

The weights of the edges make the total weights of the matchings

correspond to your objective function.

.



For ​ for each j, pick exactly a($\hspace{.015 in}$j) entries from the j-th column , ​ you'd do:

Check whether-or-not ​ ​ ​ n ​ &lt; ​ a(1) + a(2) + a(3) + ... + a(m-1) + a(m) ​ .

If that inequality is true, then there are no feasible solutions.

Otherwise, construct the bipartite graph like above but letting the edge weights be

a(1) + a(2) + a(3) + ... + a(m-1) + a(m) + 1 ​ + ​ the corresponding matrix entry ​ .

This will make it so that all maximum-weight matchings use the whole column part,

thereby indicating exactly a($\hspace{.015 in}$j) entries for each j-th column.