2
$\begingroup$

Given matrix of size N x M (N- rows, M - columns), given integer value K(K < N and K < 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&2&3&4\\4&3&2&1\\3&1&4&5\end{bmatrix}

Select column 1 and 4: \begin{bmatrix}1&4\\4&1\\3&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!

Improve this question
$\endgroup$
6
  • $\begingroup$ Can you edit the question to add a reference to the original problem? $\endgroup$
    – John L.
    Jul 1, 2019 at 5:11
  • $\begingroup$ @Apass.Jack Sorry, I don't have one. $\endgroup$
    – user107098
    Jul 1, 2019 at 6:41
  • $\begingroup$ @Apass.Jack this is from yandex contest $\endgroup$
    – user107098
    Jul 1, 2019 at 7:33
  • $\begingroup$ Then why not tell the name and the year of that Yandex context as well as the problem number or id? Per your description, an answer of NP-hard, although enlightening, does not fit the situation at all. $\endgroup$
    – John L.
    Jul 1, 2019 at 13:13
  • $\begingroup$ Let me emphasize, reference, reference and reference. Even if the source is only available in Russia or another much less popular language, a reference to it is still invaluable. $\endgroup$
    – John L.
    Jul 1, 2019 at 13:17

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ does exist any exact solution for small set (rows) number? $\endgroup$
    – user107098
    Jul 1, 2019 at 10:01
  • $\begingroup$ @user107098, I dont see any exact solution, smarter then just traversing all column permutations. Approximate solution may be found with simple greedy approximation. $\endgroup$
    – Konstantin Vladimirov
    Jul 1, 2019 at 15:14

Your Answer

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