graph-theorynetwork-flow

assignment prob flow network solution

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?

Solution

  • 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.