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:
“When I consider the clouds stretched in stupendous masses across the sky, frowning with darkness or glowing with downy light, or gilded with the rays of the setting sun, like the battlements of a city in the heavens, their grandeur appears thrown away on the meanness of my employment; the drapery is altogether too rich for such poor acting. I am hardly worthy to be a suburban dweller outside those walls.”
—Henry David Thoreau (1817–1862)
“The doctrine of those who have denied that certainty could be attained at all, has some agreement with my way of proceeding at the first setting out; but they end in being infinitely separated and opposed. For the holders of that doctrine assert simply that nothing can be known; I also assert that not much can be known in nature by the way which is now in use. But then they go on to destroy the authority of the senses and understanding; whereas I proceed to devise helps for the same.”
—Francis Bacon (1560–1626)
“Like plowing, housework makes the ground ready for the germination of family life. The kids will not invite a teacher home if beer cans litter the living room. The family isn’t likely to have breakfast together if somebody didn’t remember to buy eggs, milk, or muffins. Housework maintains an orderly setting in which family life can flourish.”
—Letty Cottin Pogrebin (20th century)