- 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.
- 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.
- 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
Asked By : user5837230
Answered By : Yuval Filmus
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/53147 3.2K people like this
