Hector
Hector

Reputation: 1220

Adapting a Ford-Fulkerson solver to include minimum weights

I have implemented a solution using Ford-Fulkerson to solve an allocation problem

Say a system where there are multiple people wanting to take part in multiple activities. Each person has a list of activities they want to do but can only be assigned one. Each activity has a capacity and is assigned to one manager. Each manager has a maximum number of people they can supervise.

I have implemented this by connecting a "source" node to each person with capacity 1. These connect to each of their list of activities capacity 1. The activities connect to the managers with the activity capacity. The managers connect to a "sink" with capacity of the managers maximum supervisees. And it works.

Now say I wanted for the sake of load balancing to assign a minimum number of people to each manager. How could I go about modifying my solution to achieve this when possible / spit out an error when not?

Thanks

Upvotes: 2

Views: 97

Answers (0)

Related Questions