The minimum cost of this matrix is inf since we can select at most 1 finite value from each of the first 2 rows, 1 finite value from each of the last 2 columns and then we must select an inf edge to complete the matching. I suppose the problem is that all matchings in the extended problem have the same sum (i.e. inf).
Hey, thanks for lapjv and lapmod, they are awesome.
I think I found a small bug. Consider the cost matrix
The minimum cost is 8 + 8 = 16. However, the result I get from
lapjv
is 18 (test case below).I guess the problem arises in the extension since
inf + 1 => inf
.The minimum cost of this matrix is
inf
since we can select at most 1 finite value from each of the first 2 rows, 1 finite value from each of the last 2 columns and then we must select aninf
edge to complete the matching. I suppose the problem is that all matchings in the extended problem have the same sum (i.e.inf
).Here is a test case: