Solving Assignment Problem on a dynamically updating tasks and agents

Question

I am having agents say A1, A2, A3, and so on. along with tasks say T1, T2, T3, and so on. I have to efficiently assign at most one task to each agent based on some parameter like T1 can be assigned to A1, A2. T2 can be assigned to A2, and A3. and T3 can be assigned to A3, and A1. I have built an unweighted bipartite graph and performed maximum cardinality matching of 1 using the max flow algorithm. Since my list of agents and tasks is changing dynamically. Is there any way where I don't have to rebuild the graph from scratch and rerun the flow algorithm? Can I use the same graph and somehow rerun the max flow algorithm?

Answer 1

It depends on what you mean by "efficiently assign".

Although you do not say, I assume that you are optimizing some calculated value that measures how "efficient" a particular solution is, compared to others.

But perhaps you will be satisfied with a very fast determination of a pretty good solution based on the optimal solution you first found, modified slightly by the change in circumstances ( e.g. assign the cheapest free agent to a new task ) The modified solution might not be optimal, but it will be close or equal. Every few changes, as the modifications of the optimal solution begin to build up, you can stop and run the whole thing again from scratch.

However, if you insist on the guaranteed optimal solution on every change, then you will have to run from scratch every time.

It all depends on whether this is a practical, real world problem you are tackling, where a pretty good, possibly even optimal, solution is fine, or if this is merely an academic exercise.