# Select a set of elements from a 2D matrix, such that each element comes from distinct row and column

We're facing following problem - an n * n 2D Matrix contains doubles (Java). Find a Set of elements such that

1. Each element in the set comes from a unique row and column combination. That is, once you've selected an element (i, j) as a candidate for a set, that set cannot contain any elements from ith row or jth column.
2. The size of the set is Maximized. The Matrix may contain NaNs, so it may not be possible to find a set of size n.
3. The sum of elements on this set is minimum over all sets of this size for this Matrix.

For Example, consider following matrix -

1 2 3 4
4 1 2 3
3 4 1 2
2 3 4 1


This is artificially constructed to demonstrate the problem, solution for this Matrix is going to be the diagonal elements

{1, 1, 1, 1}


Any ideas?

Just to be sure, this is not a homework problem. We're trying to solve this for a client. Problem we're trying to solve is in Transport domain, and basically boils down to problem statement above.

I've tried to think of a polytime solution, but the first condition seems to be problematic. If it was not in place, this would have been a trivial DP problem - create a temporary 2d array, traverse each row of original array, and for each element, try to find element in last row in temporary array that has the smallest cumulative sum. Make this element's value in temp_arr smallest cumulative sum + this element. Find smallest element in last row and you're done.

I'm trying to see if there is a polynomial time solution. In all probability, it will be easier to code, verify, and debug than any graph theory based solutions.

Edit added after some search - Just realized that what I was looking for was Hungarian Algorithm for Assignment problem - https://en.wikipedia.org/wiki/Hungarian_algorithm

• Thanks -- that looks much better, now. I'm sorry that your sensible and effective attempts to abstract out the core of the problem made me think it was a textbook exercise or homework! – David Richerby Feb 15 '16 at 19:46

• Construct a bipartite graph in which there is a vertex $R_i$ for each row and a vertex $C_j$ for each column. Add an edge between $R_i$ and $C_j$ whose weight is the $(i,j)$th entry of the matrix. Now compute a minimum matching in this graph. Make sure that you understand what matching means in this context. – Yuval Filmus Feb 15 '16 at 21:25