Intuition behind the Hungarian Algorithm

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 mm assignments are sought:

Step 0. Initialize by forming the m×m m \times m reduced cost matrix from the m×m m \times m 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 =m= m, 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 (m=3)(m=3) 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 m!m! 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 m×mm \times m assignment problem in the form of a combinatorial optimization problem. Let

cijcost of assigning worker i to task j (the original cost matrix)xij1, if worker i is assigned to task j, and 0 otherwise. \begin{aligned} c_{ij} &\equiv \text{cost of assigning worker } i \text{ to task } j \text{ (the original cost matrix)} \\ x_{ij} &\equiv 1, \text{ if worker } i \text{ is assigned to task } j \text{, and } 0 \text{ otherwise.} \\ \end{aligned}

Then a mathematical programming formulation of the assignment problem is:

min  z(1)zi=1mj=1mcijxij (total cost of an assignment of workers to tasks)subject to (2)j=1mxij=1,i{1,...,m} (one task per worker)(3)i=1mxij=1,j{1,...,m} (one worker per task)(4)xij{0,1},i,j{1,...,m} (whole assignments only) .  . \begin{aligned} \min \; &z \\ (1) \qquad &z \equiv \sum_{i=1}^m \sum_{j=1}^m c_{ij} x_{ij} \qquad \qquad \text{ (total cost of an assignment of workers to tasks)}\\ \text{subject to } & \\ (2) \qquad &\sum_{j=1}^m x_{ij} = 1 , \qquad \forall i \in \{1, ..., m\} \qquad \text{ (one task per worker)} \\ (3) \qquad &\sum_{i=1}^m x_{ij} = 1 , \qquad \forall j \in \{1, ..., m\} \qquad \text{ (one worker per task)}\\ (4) \qquad &x_{ij} \in \{0,1\} , \qquad \forall i,j \in \{1, ..., m\} \qquad \text{ (whole assignments only) .}\\ \end{aligned} \;.

Here, the objective function zz 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 {ui} \{u_i\} and {vj} \{v_j\} to somehow modify the cost matrix {cij} \{c_{ij}\} by adding and subtracting them in zz so that the total value of zz is unchanged: z=i=1mj=1mcijxij=i=1mj=1m(cijuivj+ui+vj)xij=i=1mj=1m(cijuivj)xij+i=1muij=1mxij+j=1mvji=1mxij=i=1mj=1m(cijuivj)xij+i=1mui1+j=1mvj1 (used conditions (2) and (3) ) =i=1mj=1m(cijuivj)xij+i=1mui+j=1mvj  . \begin{aligned} \qquad z &= \sum_{i=1}^m \sum_{j=1}^m c_{ij} x_{ij} \\ &= \sum_{i=1}^m \sum_{j=1}^m ( c_{ij} - u_i - v_j + u_i + v_j) x_{ij} \\ &= \sum_{i=1}^m \sum_{j=1}^m ( c_{ij} - u_i - v_j ) x_{ij} + \sum_{i=1}^m u_i \sum_{j=1}^m x_{ij}+ \sum_{j=1}^m v_j \sum_{i=1}^m x_{ij} \\ &= \sum_{i=1}^m \sum_{j=1}^m ( c_{ij} - u_i - v_j ) x_{ij} + \sum_{i=1}^m u_i \cdot 1 + \sum_{j=1}^m v_j \cdot 1 \qquad \text{ (used conditions (2) and (3) ) } \\ &= \sum_{i=1}^m \sum_{j=1}^m ( c_{ij} - u_i - v_j ) x_{ij} + \sum_{i=1}^m u_i + \sum_{j=1}^m v_j \;. \\ \end{aligned}

From this, the total cost zz can be written as (5)z=i=1mj=1mcij0xij+z0 (5) \qquad \qquad z = \sum_{i=1}^m \sum_{j=1}^m c_{ij}^0 x_{ij} + z^0 where cij0cijuivj c_{ij}^0 \equiv c_{ij} - u_i - v_j are the modified costs and z0i=1mui+j=1mvj z^0 \equiv \sum_{i=1}^m u_i + \sum_{j=1}^m v_j is a fixed cost added to the total cost expression. Now, if somehow the values of these quantities {ui} \{u_i\} and {vj} \{v_j\} are chosen so that cijuivj=cij0=0 c_{ij} - u_i - v_j = c_{ij}^0 = 0 for certain row-column indices (i,j) (i,j) that correspond to a valid assignment, then choosing xij=1 x_{ij} = 1 for these (i,j) (i,j) -indices minimizes z (and therefore solves the assignment problem!). This is because all the resulting cij0xijc_{ij}^0 x_{ij} terms for zz in (5) (5) are 0 since either cij0=0c_{ij}^0 =0 when xij=1x_{ij} = 1 or xij=0 x_{ij} = 0, in which case (5) (5) reduces to z=z0z = z^0, a quantity independent of variables xx, and the minimum value of a constant is just the constant.

What are these mysterious quantities {ui} \{u_i\} and {vj} \{v_j\} ?
First observe that they are the sole contributor to the optimal total cost since z=z0=i=1mui+j=1mvjz = z^0 = \sum_{i=1}^m u_i + \sum_{j=1}^m v_j . Second, in the expression cijui c_{ij} - u_i for a fixed ii, ui u_i is subtracted from cij c_{ij} for every jj; in other words, ui u_i is the quantity subtracted from row ii of the cost matrix {cij} \{c_{ij} \} . Similarly, vjv_j is the quantity subtracted from column jj of the matrix that results from subtracting uiu_i from row ii of the matrix {cij} \{c_{ij}\} . The resulting matrix has elements cijuivj c_{ij} - u_i -v_j (the final reduced cost matrix elements). Therefore, the quantities {ui} \{u_i\} and {vj} \{v_j\} 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 z0z^0 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" {ui} \{u_i\} and {vj} \{v_j\} 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 {ui} \{u_i\} and {vj} \{v_j\} 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].

#Combinatorics

Note by Wesley Zumino
3 years, 9 months ago

No vote yet
1 vote

  Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

  • Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
  • Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
  • Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

Hi Wesley -- this is fantastic! Would you mind if we merge some of this content into here? It will leave this discussion unchanged.

Eli Ross Staff - 3 years, 9 months ago

Log in to reply

Eli - no prob at all. Actually, I had considered that myself but, being new here, I was concerned about making any changes to Karleigh and Nathan's work that might have to be made to smooth this material in. FYI, the content of this note is original (at least I haven't seen it before), so there are no copyright issues. I did get some inspiration from Murty's text.

And thank you very much for the kind sentiments!

Wesley Zumino - 3 years, 9 months ago
×

Problem Loading...

Note Loading...

Set Loading...