AjaySabarish's blog

By AjaySabarish, history, 3 years ago, In English

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?

  • Vote: I like it
  • +13
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it +24 Vote: I do not like it
»
3 years ago, # |
Rev. 5   Vote: I like it +34 Vote: I do not like it

I think the Hungarian Algorithm solves this problem. Time complexity is around O((N^2)M). Here's a video on it by SecondThreadhttps://www.youtube.com/watch?v=cVBzMXYc4ss&t=1566s

»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

greedy with kuhn algorithm should work

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

    No. Only if for each A Cost[A][i] = Cost[A][j] for every i, j

»
3 years ago, # |
Rev. 2   Vote: I like it +11 Vote: I do not like it

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.