Setting
We are given a nonnegative n×n matrix, where the element in the i-th row and j-th column represents the cost of assigning the j-th job to the i-th worker. We have to find an assignment of the jobs to the workers that has minimum cost. If the goal is to find the assignment that yields the maximum cost, the problem can be altered to fit the setting by replacing each cost with the maximum cost subtracted by the cost.
The algorithm is easier to describe if we formulate the problem using a bipartite graph. We have a complete bipartite graph G=(S, T; E) with n worker vertices (S) and n job vertices (T), and each edge has a nonnegative cost c(i,j). We want to find a perfect matching with minimum cost.
Let us call a function a potential if for each . The value of potential y is . It can be seen that the cost of each perfect matching is at least the value of each potential. The Hungarian method finds a perfect matching and a potential with equal cost/value which proves the optimality of both. In fact it finds a perfect matching of tight edges: an edge ij is called tight for a potential y if . Let us denote the subgraph of tight edges by . The cost of a perfect matching in (if there is one) equals the value of y.
Read more about this topic: Hungarian Algorithm
Famous quotes containing the word setting:
“Love is at the root of all healthy discipline. The desire to be loved is a powerful motivation for children to behave in ways that give their parents pleasure rather than displeasure. it may even be our own long-ago fear of losing our parents’ love that now sometimes makes us uneasy about setting and maintaining limits. We’re afraid we’ll lose the love of our children when we don’t let them have their way.”
—Fred Rogers (20th century)
“The setting sun is reflected from the windows of the alms-house as brightly as from the rich man’s abode; the snow melts before its door as early in the spring. I do not see but a quiet mind may live as contentedly there, and have as cheering thoughts, as in a palace.”
—Henry David Thoreau (1817–1862)
“We don’t arrive at it by standing on one leg or on the first day of our setting out—but though we may jostle one another on the way that is no reason why we should strike or trample—elbowing’s enough.”
—George Gordon Noel Byron (1788–1824)