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


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.