There are M objects of type 1 and N objects of Type 2. Given $$$Cost[i][j]$$$ where $$$i$$$ is an object of Type 1, and $$$j$$$ is an object of Type 2. What is the minimum total cost achievable after every type 1 object is mapped with exactly one type 2 object?
Total cost is defined as the summation of the individual costs incurred due to matching.
$$$M <= N$$$.
Example :
Type 1 : $$$A B$$$
Type 2 : $$$C D$$$
$$$cost[A][C] = 100$$$
$$$cost[A][D] = 10$$$
$$$cost[B][C] = 10$$$
$$$cost[B][D] = 100.$$$
It's optimal to match $$$(A, D)$$$ and $$$(B, C)$$$, the total cost incurred is 20.
I thought of a bit masking + DP approach, but the complexity is exponential, is there a better approach?
I'm only 90% sure this would work:
https://cp-algorithms.com/graph/Assignment-problem-min-flow.html
I think the Hungarian Algorithm solves this problem. Time complexity is around O((N^2)M). Here's a video on it by SecondThread — https://www.youtube.com/watch?v=cVBzMXYc4ss&t=1566s
greedy with kuhn algorithm should work
No. Only if for each A Cost[A][i] = Cost[A][j] for every i, j
You could use mincost-flow. Construct a source S and drain T, then for every node if it is of type 1, then add an edge from S to it with bandwidth 1 and cost 0;else add an edge from it to T with bandwidth 1 and cost 0. And for edges(a,b) (a is type 1, b is type 2) in the original graph, make sure to only add an edge from the type-1 node to the type-2 node with bandwidth 1 and cost cost[a][b] in the new graph. All Then run mincost-flow from S to T.
The time complexity is O(n^5) but it usually runs close to O(n*sqrt(m)) on these bipartite graphs. I've solved problems with n,m<=10^5 with this.