Minimum k elements of an mxn matrix, with the restriction that none of the elements can be in the same row/column

3
votes

I have a dynamic programming (possibly greedy) question.

Let A be an mxn matrix. Let k be an integer such that k ≤ min{m,n}.

Find k elements of A such that each of these k elements are in their unique column and row; and the sum of these k elements is minimized.

In other words, I want to pick k elements from A such that their sum is minimal; but if I select A2,3 then I cannot select A2,6 or A4,3.

A greedy approach seems to be selecting the minimum element in A, removing its row and column, and repeating until A is 'depleted'. However I am unable to prove the greedy choice property in this case, or if it even has the greedy choice property.

I also could not figure out how to build a table for a DP solution.

If this problem has been posed previously and has a specific name, can you please share it?

2
algorithmmatrixdynamic-programming
(For simplicity we can consider the case where k=n=m) – kubuzetto
This is min-weight bipartite matching. No, greedy doesn't work. – tmyklebu
Wonderful pointer sir/madam, thank you. – kubuzetto

2 Answers

5
votes

Greedy won't cut it. You need the Hungarian Algorithm machinery. One can think about creating n - k new rows and m - k new columns, making the new-row–new-column entries very unattractive and the other new entries very attractive. Then find a min-cost solution that matches the rows with the columns one-to-one and throw away the pairs containing a new row or column.

In actual practice, there will be a better implementation, but describing it requires me to recap the details of the HA.

2
votes

The greedy algorithm won't give an optimal solution. Assume A11 = 0, A12 = A21 = 1, everything else = 1000. The smallest sum is found by taking A12, A21, and any k-2 other values, total 1000k - 1998. Picking A11 = 0 first forces you to pick k-1 values of 1000, for a total of 1000k - 999.