Assignment Problem Hungarian Method Maximization

By continuing to use this site, you consent to the use of cookies.

By continuing to use this site, you consent to the use of cookies.

But, due to the specifics of the problem, there are more efficient algorithms to solve it.

We’ll handle the assignment problem with the Hungarian algorithm (or Kuhn-Munkres algorithm).

To learn more or modify/prevent the use of cookies, see our Cookie Policy and Privacy Policy.

Discuss this article in the forums Are you familiar with the following situation?

Obviously, these edges will be the solution of the assignment problem.

If we can’t find perfect matching on the current step, then the Hungarian algorithm changes weights of the available edges in such a way that the new 0-weight edges appear and these changes do not influence the optimal solution.The assignment problem is a special case of the transportation problem, which in turn is a special case of the min-cost flow problem, so it can be solved using algorithms that solve the more general cases.Also, our problem is a special case of binary integer linear programming problem (which is NP-hard).I’ll illustrate two different implementations of this algorithm, both graph theoretic, one easy and fast to implement with O(n4) complexity, and the other one with O(n3) complexity, but harder to implement.There are also implementations of Hungarian algorithm that do not use graph theory.Now we’re ready for the theorem which provides the connection between equality subgraphs and maximum-weighted matching: is called alternating if its edges alternate between M and E\M.(For example, (W4, J4, W3, J3, W2, J2) and (W4, J1, W1) are alternating paths)If the first and last vertices in alternating path are exposed, it is called (because we can increment the size of the matching by inverting edges along this path, therefore matching unmatched edges and vice versa). And now let’s illustrate these steps by considering an example and writing some code.For each pair (worker, job) we know salary that should be paid to worker for him to perform the job. Then our task is to find minimum-weight matching in the graph (the matching will consists of N edges, because our bipartite graph is complete).Our goal is to complete all jobs minimizing total inputs, while assigning each worker to exactly one job and vice versa. Small example just to make things clearer: This problem is known as the assignment problem.In other words, the sum of the labels of the vertices on both sides of a given edge are greater than or equal to the weight of that edge.be a spanning subgraph of G (in other words, it includes all vertices from G).