Solve Assignment Problem Online
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.
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.
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.
(Example on the picture above, with root in W4)That’s all for the theory, now let’s look at the algorithm: First let’s have a look on the scheme of the Hungarian algorithm: Step 0. (See Picture 1)Picture 1Here are the global variables that will be used in the code:#define N 55 //max number of vertices in one part#define INF 100000000 //just infinityint cost[N][N]; //cost matrixint n, max_match; //n workers and n jobsint lx[N], ly[N]; //labels of X and Y partsint xy[N]; //xy[x] - vertex that is matched with x,int yx[N]; //yx[y] - vertex that is matched with ybool S[N], T[N]; //sets S and T in algorithmint slack[N]; //as in the algorithm descriptionint slackx[N]; //slackx[y] such a vertex, that// l(slackx[y]) l(y) - w(slackx[y],y) = slack[y]int prev[N]; //array for memorizing alternating paths It’s easy to see that next initial labeling will be feasible: And as an initial matching we’ll use an empty one. The code for initializing is quite easy, but I’ll paste it for completeness: The next three steps will be implemented in one function, which will correspond to a single iteration of the algorithm.
Find some initial feasible vertex labeling and some initial matching. If M is perfect, then it’s optimal, so problem is solved. (x – is a root of the alternating tree we’re going to build). When the algorithm halts, we will have a perfect matching, that's why we'll have n iterations of the algorithm and therefore (n 1) calls of the function.
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).Then, after the contest, you find out in the editorial that this problem can be simply reduced to a classical one.If yes, then this tutorial will surely be useful for you. We can also rephrase this problem in terms of graph theory.See picture below for explanation: At last, here's the function that implements Hungarian algorithm: To see all this in practice let's complete the example started on step 0.| Build alternating tree V| Augmenting V path found| Build V alternating tree| Update V labels(Δ=1)| Build alternating V tree| Update V labels(Δ=1)→| Build V alternating tree| Augmenting V path found| Build V alternating tree| Update labels V (Δ=2)| Build V alternating tree| Update labels V (Δ=1)| Build V alternating tree| Augmenting V path found Optimalmatching found Finally, let's talk about the complexity of this algorithm.On each iteration we increment matching so we have n iterations.For each vertex from left part (workers) find the minimal outgoing edge and subtract its weight from all weights connected with this vertex. Actually, this step is not necessary, but it decreases the number of main cycle iterations. Find the maximum matching using only 0-weight edges (for this purpose you can use max-flow algorithm, augmenting path algorithm, etc.). Step 2) Let and adjust the weights using the following rule: Step 3) Repeat Step 1 until solved.But there is a nuance here; finding the maximum matching in step 1 on each iteration will cause the algorithm to become O(n5).The main idea of the method is the following: consider we’ve found the perfect matching using only edges of weight 0 (hereinafter called “0-weight edges”).Obviously, these edges will be the solution of the assignment problem.be a spanning subgraph of G (in other words, it includes all vertices from G).If G only those edges (x,y) which satisfy the following condition: , then it is an equality subgraph.