2
$\begingroup$

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

Improve this question
$\endgroup$
1
  • $\begingroup$ 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! $\endgroup$
    – David Richerby
    Feb 15, 2016 at 19:46

1 Answer 1

Reset to default
2
$\begingroup$

This is maximum matching in a weighted bipartite graph in disguise. (You can easily convert your objective of minimizing the sum of weights into one of maximizing it.)

Improve this answer
$\endgroup$
8
  • $\begingroup$ Hi, Thanks for reply. Trying to see if this is about finding minimum weight matching in a k-partitie graph (as opposed to a bipartite graph). All the elements in the same row or column are in same partition, and this problem reduces to finding minimum wight matching that has maximum edges? $\endgroup$
    – user5837230
    Feb 15, 2016 at 20:53
  • $\begingroup$ No, your problem is exactly minimum matching in a weighted bipartite graph. The two parts are the rows and the columns. $\endgroup$
    – Yuval Filmus
    Feb 15, 2016 at 21:10
  • $\begingroup$ Hi, Thanks for the second reply. Sorry, but I'm still not clear on the approach. Obviously, elements on same row or column need to be in same partition, but I don't see how a single partition can be created for all rows. I've added an example to the description of the problem, just in case the problem statement was not descriptive enough. $\endgroup$
    – user5837230
    Feb 15, 2016 at 21:23
  • 1
    $\begingroup$ 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. $\endgroup$
    – Yuval Filmus
    Feb 15, 2016 at 21:25
  • $\begingroup$ Bah! You're right. I'm certain it is, but just to be sure, this is the most efficient solution to this problem, right? $\endgroup$
    – user5837230
    Feb 15, 2016 at 21:34

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.

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