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:
“Teaching Black Studies, I find that students are quick to label a black person who has grown up in a predominantly white setting and attended similar schools as “not black enough.” ...Our concept of black experience has been too narrow and constricting.”
—bell hooks (b. c. 1955)
“A happy marriage perhaps represents the ideal of human relationship—a setting in which each partner, while acknowledging the need of the other, feels free to be what he or she by nature is: a relationship in which instinct as well as intellect can find expression; in which giving and taking are equal; in which each accepts the other, and I confronts Thou.”
—Anthony Storr (b. 1920)
“Dandyism is the last flicker of heroism in decadent ages.... Dandyism is a setting sun; like the declining star, it is magnificent, without heat and full of melancholy. But alas! the rising tide of democracy, which spreads everywhere and reduces everything to the same level, is daily carrying away these last champions of human pride, and submerging, in the waters of oblivion, the last traces of these remarkable myrmidons.”
—Charles Baudelaire (1821–1867)