assignment prob flow network solution

Question

I have an assignment problem with cost matrix C, eg:

21 30 26 16 20
27 29 28 20 38
39 25 21 19 23
28 24 30 29 16
30 33 32 17 31

where C[i][j] means cost for worker i to do job j.

How can I solve this with a network flow algorithm? I would welcome any hints.

Answer 1

In case you are still looking for a solution, you can solve this as a Minimum-cost flow problem:

1. Create a source node connected to your N workers by edges with capacity 1 and cost 0
2. Connect each worker i to each job j by edges of capacity 1 and cost C[i][j]
3. Finally connect each job to a sink node with edges of capacity 1 and cost 0

Your problem is equivalent to minimizing the cost of pushing N flow units through the network from source to sink.