In other words, it only includes those edges from the bipartite matching which allow the vertices to be perfectly feasible.
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.
In order to avoid this, on each step we can just modify the matching from the previous step, which only takes O(n2) operations.
It’s easy to see that no more than n2 iterations will occur, because every time at least one edge becomes 0-weight. This is simply a function (for each vertex we assign some number called a label).
The only thing in code that hasn't been explained yet is the procedure that goes after labels are updated.
Say we've updated labels and now we need to complete our alternating tree; to do this and to keep algorithm in O(n3) time (it's only possible if we use each edge no more than one time per iteration) we need to know what edges should be added without iterating through all of them, and the answer for this question is to use BFS to add edges only from those vertices in Y, that are not in T and for which slack[y] = 0 (it's easy to prove that in such way we'll add all edges and keep algorithm to be O(n3)).
We’ll handle the assignment problem with the Hungarian algorithm (or Kuhn-Munkres algorithm).
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.
In this article we’ll deal with one optimization problem, which can be informally defined as: Assume that we have N workers and N jobs that should be done. Let’s look at the job and workers as if they were a bipartite graph, where each edge between the .
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).