The Hungarian Algorithm (Also Munkres' Assignment Algorithm)

Question

I've stumbled on this algorithm recently and am having difficulty explaining it to myself. The algorithm solves the assignment problem in O(n⁴) (and apparently can be improved to O(n³)) but I can't see why.

Intuitively I can see that the algorithm would tend to find good to optimal solutions but I can't see a proof! All the proofs I have seen so far contain notation I am unfamiliar with. My question is: can anyone explain it rigorously but simply?

I understand already that the problem can be transferred to a matrix of values where exactly one value in each row and each column must be selected. The minimum value possible (from the selected elements) and the selection that produces that is what the algorithm computes. Obviously finding the selection also finds the minimum.

---

The part I'm struggling on, notation-wise, is here. The third paragraph down in the Settings section which begins "Let us call a function"...

Answer 1

The Wikipedia page you linked to has steps on how to do this algorithm by hand on a matrix. The python implementation also uses matrices. Sometimes the only way to understand an algorithm is to step through it by hand or in the interactive console.

Answer 2

That's saying y of the S and T values is a potential answer if y at i and y at j are together less than the cost calculated for that position so far (finding lowest potential answer), for every position in S and T.

This is a dynamic programming problem, if I recall correctly. A perfect matching would be when the guy whose cheapest rate happens to be what he is picked to do.

Answer 3

The function is mapping each vertex in the graph, which is the union of S and T which is what that U-shaped symbol means, into the rational number system which is what that Q represents by that inequality for a given pair of vertices. What part of the notation there doesn't make sense still?

Answer 4

The potential function y assigns a number to every vertex in your complete bipartite graph in such a way, that the sum of potentials of any vertex from S (the set of all people) and any vertex from T (the set of all jobs) is smaller than the value of the edge connecting these vertices (so smaller than the cost of the person doing the job). A function that assigns 0 to every vertex is a good example of a valid potential function.

The value of potential y is the sum of the potentials of all vertices (this is the definition).

It can be seen that the cost of each perfect matching is at least the value of each potential.

This is fairly obvious: in perfect matching you have to pick n edges that don't have common vertices. Cost of every edge is lower than the sum of the potential of its vertices (from definition of potential). When you sum the costs of all edges from your matching, it will be higher than the value of potential for the graph.

Now, the algorithm computes an potential and a matching, such that they cost/value is the same. Because the value of potential is the lower bound of the minimum cost for the problem, you get an optimal solution.

This proves the algorithm. Now you need to look at it and understand why and how it finds a perfect matching and a potential with equal cost/value.

Answer 5

You might check out this book by Jungnickel which contains a thorough theoretical discussion of the Hungarian algorithm starting on p 421, but also works out an example. By working through the example, you should be able see why the algorithm is O(n3)).