The Hungarian Algorithm (see here, here, or here) is an easy-to-perform method for solving an assignment problem, a well-studied problem in the field of combinatorial optimization. An example of a simple assignment problem is the following: Example: A company wants to temporarily hire 3 workers to do 3 tasks at the same time. The cost each worker charges to do each task is as shown in the table. How should the company assign the workers to the tasks to minimize its total cost?
Here is a summary of the Hungarian Algorithm when assignments are sought:
Step 0. Initialize by forming the reduced cost matrix from the cost matrix as follows: For each row, subtract the minimum matrix element in the row from all elements in the row. For each column, subtract the minimum matrix element in the column from all elements in the column.
Step 1. Draw the minimal number of horizontal and vertical lines to cover all zeros in the matrix. If the number of lines , STOP: an optimal (least cost) assignment is available from among the zero matrix elements of the final reduced cost matrix. Otherwise, continue to Step 2.
Step 2. Find the minimum uncovered element. Subtract this element from each uncovered element. Add this element to each twice-covered element. (Equivalently, subtract the minimum from all uncovered rows and then add it to all covered columns.) Go to Step 1.
The algorithm is illustrated in the figures below (left to right) for the posed assignment problem (sorry only small figs allowed - click to zoom).
The Hungarian Algorithm applied to the example problem results in an optimal assignment with a total cost of 900, as can be checked by using brute force to check the total costs of all possible assignments. One question that could be asked is why the resulting assignment is optimal, i.e., why does the Hungarian Algorithm work? The purpose of this note is to informally address this question and try to provide intuitive motivation of the algorithm's correctness.
First, write an assignment problem in the form of a combinatorial optimization problem. Let
Then a mathematical programming formulation of the assignment problem is:
Here, the objective function in (1) is the total cost of assigning all workers to tasks and is to be minimized. The two equality conditions impose the distinct pairing between workers and tasks that makes the workers-to-tasks assignment valid, i.e., exactly one task to each worker (2) and exactly one worker to each task (3). The last condition (4) simply requires assignments to be whole and complete, not partial as in one worker does half of a task and another does the other half (i.e., it is an integer linear program).
Now, as seen in the example, the Hungarian algorithm appears to operate entirely on the cost matrix for the problem. So, suppose we introduce quantities and to somehow modify the cost matrix by adding and subtracting them in so that the total value of is unchanged:
From this, the total cost can be written as where are the modified costs and is a fixed cost added to the total cost expression. Now, if somehow the values of these quantities and are chosen so that for certain row-column indices that correspond to a valid assignment, then choosing for these -indices minimizes z (and therefore solves the assignment problem!). This is because all the resulting terms for in are 0 since either when or , in which case reduces to , a quantity independent of variables , and the minimum value of a constant is just the constant.
What are these mysterious quantities and ?
First observe that they are the sole contributor to the optimal total cost since . Second, in the expression for a fixed , is subtracted from for every ; in other words, is the quantity subtracted from row of the cost matrix . Similarly, is the quantity subtracted from column of the matrix that results from subtracting from row of the matrix . The resulting matrix has elements (the final reduced cost matrix elements). Therefore, the quantities and are the total amounts determined by the Hungarian Algorithm that when subtracted from the rows and columns, respectively, of the original cost matrix will result in an optimal assignment (based on the final reduced cost matrix). It can be verified in the example problem that when all the row, column, and uncovered element minimums are totaled, the result is the minimum cost: 250 + 350 + 200 + 0 + 50 + 0 + 50 = 900! So, the Hungarian Algorithm operation can be thought of as systematically transferring cost to from the original cost matrix for those matrix elements that will end up being candidate costs in a minimum cost assignment.
Hopefully the foregoing suggests why the Hungarian Algorithm gives rise to an optimal assignment. How it comes up with these "subtractors" and requires a deeper discussion involving duality theory: every linear program has a companion linear program called its dual that is solved simultaneously, and in the case of the assignment problem, the and are the dual variables. Interested readers can consult K. Murty's excellent free online book Network Programming, specifically the first 8 or so pages of Chapter 3. [Note that Prof. Murty's presentation of the Hungarian Algorithm is an equivalent but different version than the above, but it is the discussion leading up to the algorithm presentation you might find particularly insightful].