Search code examples
algorithmgraphgraph-algorithmnetwork-flowford-fulkerson

Assigning jobs to people using Maximum Flow, harder version

I am self studying max flow and there was this problem:

the original problem is

  • Suppose we have a list of jobs

    {J1, J1,..., Jm}

  • and a list of people that have applied for them

    {P1, P2, P3,...,Pn}

  • each person have different interests and some of them have applied for multiple jobs (each person has a list of jobs they can do)

  • nobody is allowed to do more than 3 jobs.

so, this problem can be solved by finding a maximum flow in the graph below enter image description here

I understand this solution, but

the harder version of the problem

what if these conditions are added?

  • the first 3 conditions of the easy version (lists of jobs and persons and each person has a list of interests or abilities) are still the same

  • the compony is employing only Vi persons for job Ji

  • the compony wants to employ as many people as possible

  • there is no limitations for the number of jobs a person is allowed to do.

What difference should I make in the graph so that my solution can satisfy those conditions as well?or if I need a different approach please tell me.

before anyone say anything, this is not homework. It's just self study, but I am studying Maximum flow and the problem was in that area so the solution should use Maximum flow.

Solution

    • For multiple persons for a single job:

      The edge from Ji to t will have the capacity equal to the number of people for that job. E.g. If job #1 can have three people, this translates to a capacity of three for the edge from J1 to t.

    • For the requirement of hiring as many people as possible:

      I don't think this is possible with a single flow-graph. Here is an algorithm for how it could be done:

      1. Run the flow-algorithm once.
      2. For each person:
        1. Try to decrease the incoming capacity to one below the current flow-rate.
        2. Run the flow-algorithm again.
        3. While this does not decrease the total flow, repeat from (2.1.).
        4. Increase the capacity by one, to restore the maximum flow.
      3. Until no further persons gets added, repeat from (2.).
         

    • For no limitation on number of jobs:

      The edges from s to Pi will have a maximum flow equal the number of applicable jobs for that person.