Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

A question was posted on Stack Overflow asking for an algorithm to solve this problem:

I have a matrix (call it A) which is nxn. I wish to select a subset (call it B) of points from matrix A. The subset will consist of n elements, where one and only one element is taken from each row and from each column of A. The output should provide a solution (B) such that the sum of the elements that make up B is the maximum possible value, given these constraints (eg. 25 in the example below). If multiple instances of B are found (ie. different solutions which give the same maximum sum) the solution for B which has the largest minimum element should be selected.

B could also be a selection matrix which is nxn, but where only the n desired elements are non-zero.

For example: if A =

|5 4 3 2 1|
|4 3 2 1 5|
|3 2 1 5 4|
|2 1 5 4 3|
|1 5 4 3 2|

=> B would be

 |5 5 5 5 5|

I proposed a dynamic programming solution which I suspect is as efficient as any solution is going to get. I've copy-pasted my proposed algorithm below.


  • Let $A$ be a square array of $n$ by $n$ numbers.
  • Let $A_{i,j}$ denote the element of $A$ in the ith row and jth column.
  • Let $S( i_1:i_2, j_1:j_2 )$ denote the optimal sum of non-overlapping numbers for a square subarray of $A$ containing the intersection of rows $i_1$ to $i_2$ and columns $j_1$ to $j_2$.

Then the optimal sum of non-overlapping numbers is denoted S( 1:n , 1:n ) and is given as follows:

$$S( 1:n , 1:n ) = \max \left \{ \begin{array}{l} S( 2:n , 2:n ) + A_{1,1} \\ S( 2:n , 1:n-1 ) + A_{1,n} \\ S( 1:n-1 , 2:n ) + A_{n,1} \\ S( 1:n-1 , 1:n-1 ) + A_{n,n} \\ \end{array} \right.$$

Note that S( i:i, j:j ) is simply Aij.

That is, the optimal sum for a square array of size n can be determined by separately computing the optimal sum for each of the four sub-arrays of size n-1, and then maximising the sum of the sub-array and the element that was "left out".

S for |# # # #|
      |# # # #|
      |# # # #|
      |# # # #|

Is the best of the sums S for:

|#      |      |      #|      |# # #  |       |  # # #|
|  # # #|      |# # #  |      |# # #  |       |  # # #|
|  # # #|      |# # #  |      |# # #  |       |  # # #|
|  # # #|      |# # #  |      |      #|       |#      |

This is a very elegant algorithm and I strongly suspect that it is correct, but I can't come up with a way to prove it is correct.

The main difficulty I am having it proving that the problem displays optimal substructure. I believe that if the four potential choices in each calculation are the only four choices, then this is enough to show optimal substructure. That is, I need to prove that this:

|   #    |
| #   # #|
| #   # #| 
| #   # #|

Is not a valid solution, either because it's impossible (i.e. proof by contradiction) or because this possibility is already accounted for by one of the four "n-1 square" variations.

Can anyone point out any flaws in my algorithm, or provide a proof that it really does work?

share|improve this question
    
But what is time complexity of your algorithm? –  user742 Apr 30 '12 at 21:21
    
Maximum matching? –  Aryabhata Apr 30 '12 at 21:46
    
@SaeedAmiri: Thanks for the LaTeX markup. And it would have been O(N^3) if it worked, except it doesn't work. So pooh. –  Li-aung Yip May 1 '12 at 0:21
    
Unless I'm misunderstanding something, a straightforward reduction from Traveling Salesman implies that the original problem is NP-hard! –  JeffE May 1 '12 at 20:04
    
@JeffE: Could you elaborate in answer form? –  Li-aung Yip May 2 '12 at 1:08

2 Answers 2

up vote 6 down vote accepted

Actually, I don't believe your proposed solution is correct. An example where you might need this case

|   #    |
| #   # #|
| #   # #| 
| #   # #|

might be

| 1 2 1 1|
| 2 1 1 1|
| 1 1 1 2| 
| 1 1 2 1|

The optimal solution consists of all 2s, while there are only 1s in the corners; therefore, you cannot find an optimal solution just by starting at the corners.

share|improve this answer
    
Ouch. Damnation. –  Li-aung Yip May 1 '12 at 0:19

This problem can be solved by maximum matching algorithm in weighted bipartite graph, such as Kuhn-Munkres algorithm or minimum cost flow algorithm.

Imagine a bipartite graph $G$, whose two disjoint point sets are $A$ and $B$. Each vertex $a_i \in A$ corresponds to a row, and each vertex $b_j \in B$ corresponds to a column. The weight of edge $E_{i,j}$ between $a_i$ and $b_j$ is $M_{i, j}$, the $j$-th element of $i$-th row of the matrix. The weighted max matching of this graph corresponds to a solution to your problem.

To break the tie, you have to find the value of max weighted matching at first. Let the value be $W_{max}$. Then you should sort all the elements in matrix $M$ and make a binary search on it. When testing the value $m$, i.e., whether there is a max matching whose minimum element is no less than $m$, you should modify all $M_{i, j}$ to $-\infty$ if $M_{i, j} < m$ and find the max matching $W_{max}'$ in the modified matrix $M'$. $W_{max}' = W_{max}$ iff there is a solution whose min elements in no less than $m$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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