7
$\begingroup$

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?

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

2 Answers 2

7
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Ouch. Damnation. $\endgroup$ May 1, 2012 at 0:19
5
$\begingroup$

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$.

$\endgroup$

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.