Select K columns from matrix and one element from each row that has maximum sum Given matrix of size N x M (N- rows, M - columns), given integer value K(K &lt; N and K &lt; M). Select arbitrary K columns and create new matrix of size N x K after that select max element from each row and calculate sum - S. Task is to find such K columns, so that this sum S will be maximum for given matrix N x M and value K. 

Example:

K: 2
Matrix:
\begin{bmatrix}1&amp;2&amp;3&amp;4\\4&amp;3&amp;2&amp;1\\3&amp;1&amp;4&amp;5\end{bmatrix}

Select column 1 and 4:
\begin{bmatrix}1&amp;4\\4&amp;1\\3&amp;5\end{bmatrix}

Select maximum values from rows:
\begin{bmatrix}4\\4\\5\end{bmatrix}

We got sum 13, this is maximum sum for given matrix and for given K.

It looks similar weighted assignment problem or weighted bipartite matching, but I don't know how to reduce this task to them. 

Thank you!
There is trivial reduction from set cover. Consider 0-1 matrix where columns are subsets, rows are set elements and 1 means that subset contains element. Algorithm for your problem then can find K subsets to cover (sum max elements to n) set.

So your problem is NP-hard, no chances.