**The Problem:**

Given a set of people and a set of jobs, where each person may take a different amount of time to do each job, optimally match people to jobs (1:1) to minimize the amount of time it will take to complete all jobs.

Many people will recognize this as a standard matching problem for which the Hungarian Algorithm is a known solution. But for those that have implemented the Hungarian Algorithm (or seen implementations of it), you know well enough to steer clear. It is error prone, and a very specific algorithm. So, I sought to implement a more elegant (and generally applicable) solution using graphs.

I found this article over on topcoder describing max-flow algorithms and the beauty of such. I fell in love and decided that I needed to solve this with max-flow.

**The formulation:**

Lets convert our problem to a bipartite graph. Let one set of nodes be the people, and the other set of nodes be the jobs. Create an edge from each person to each job, with a weight (NOT capacity!) equal to the time it will take that person to do that job.

In our situation, the capacity for each line is one since only one person can do a job. Flow is ofcourse initialized to zero for each edge (no one is doing any of the jobs). Lastly, we connect every job to a SINK node in the graph.

**The philosophy and algorithm: (the important part)**

Essentially, we'll be finding shortest paths in the graph, from each person to the SINK (via jobs) iterating through each of the people. On each iteration, we augment the graph with the path.

To recap the topcoder article, augmenting the graph consists of incrementing the flow for each edge in the augmenting path and adjusting edges to represent the new flow/capacity. There is an edge that represents "residual capacity" with capacity == capacity - flow, and there is an edge in the reverse direction that represents "upstream flow" with capacity == flow.

**REMEMBER, in our case:**

Capacity is ALWAYS 1.

Flow is either 1 or 0.

This is ENTIRELY independent of the cost/value/weight of an edge.

What does that mean to us you say? Well, in our case there are only two situations, a person is assigned to a job (flow == 1), or a person is not assigned ot a job (flow == 0). In the first case, where a person is assigned a job, there is an edge from the job to the person. During the algorithm, this edge essentially represents the path to UNDO the assignment. In the second case, the edge simply represents the

making that assignment.

## 3 comments:

Pretty good post. I just came across your site and wanted to say that I’ve really enjoyed reading your posts. In any case I’ll be subscribing to your feed and I hope you will keep a good work!Cheer!

sap online training

software online training

sap sd online training

hadoop online training

sap-crm-online-training

This is one awesome blog article. Much thanks again.

I really enjoy the blog.Much thanks again. Really Great.

oracle online training

sap fico online training

dotnet online training

qa-qtp-software-testing-training-tutorial

Great and Useful Article.

Online Java Training

Java Online Training India

Java Online Course

Java EE course

Java EE training

Best Recommended books for Spring framework

Java Interview Questions

Java Course in Chennai

Java Online Training India

Post a Comment