Select certain number of column elements of a stochastic matrix, maximum one element per row

Question

Consider a $m \times n$ Matrix.
Every column represents a class and every row an observation. Every row/observation is a probability distribution, hence every row sums up to 1. We now want to choose elements $a_{i,j}$ of the Matrix.
For every column $k_j$ elements have to be chosen, but we can choose just one element per row. The sum of the chosen elements have to be maximized.

I guess this problem is NP-hard. I didn't found an efficient solution. To prove that, I want to find a reduction from a NP-hard problem to my problem.

Hopefully someone has an idea for a reduction (or an efficient algorithm).

Answer 1

Duplicate the $j$th column $k_j$ times to reduce to the case in which $k_j = 1$. You are now looking at the assignment problem, which can be solved efficiently.