# 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:

2. Is the corresponding decision problem NP-complete?
3. Do you know an efficient algorithm to solve the problem?
4. 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:

1. $\forall j \in \{1, \ldots m\} \colon \lvert T^{-1}(j)\rvert = a(j)$
2. 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

.

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 ​ < ​ 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.