Maximise sum of "non-overlapping" numbers in square array - help with proof

Question

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?

Answer 1

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.

Answer 2

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