Hungarian Algorithm Example

Given an $N\times N$ cost matrix, find a perfect matching (one-to-one assignment of agents to tasks) with minimum total cost.

The problem is modeled as a weighted bipartite graph, with agents on one side and tasks on the other. The goal is to find a perfect matching that minimizes the sum of weights (costs).

Original Cost Matrix

The original cost matrix:

Can be represented mathematically as $C=[c_{ij}]$:

$$C=\left[\begin{array}{ccccc}11& 7& 10& 17& 10\\ 13& 21& 7& 11& 13\\ 13& 13& 15& 13& 14\\ 18& 10& 13& 16& 14\\ 12& 8& 16& 19& 10\end{array}\right]$$

Where $i\in [1,5]$ indexes rows (agents), and $j\in [1,5]$ indexes columns (tasks).

Step 1: Row Reduction (Initialize $u_i$)

Initialize potentials $u_i=\min ({\text{row}}_i)$, and subtract from each row to ensure every row has at least one zero. This builds a feasible dual solution and begins construction of the equality graph, which consists of zero-weight edges.

For each row $i$, find the minimum element and subtract it from all entries in that row:

$$u_i=\underset{j}{\min }{c}_{ij}$$

This ensures every row has at least one zero, reducing the matrix while preserving the relative cost differences between assignments. Additionally, this subtraction initialises a feasible labelling for $u_i$.

This transforms the cost matrix into one where each row has a zero, making it easier to build an equality graph, which contains only zero-weight edges.

$$u_i=\left[\begin{array}{c}7\\ 7\\ 13\\ 10\\ 8\end{array}\right]⟶C^{\prime }=C-u_i⟶C^{\prime }=\left[\begin{array}{ccccc}4& 0& 3& 10& 3\\ 6& 14& 0& 4& 6\\ 0& 0& 2& 0& 1\\ 8& 0& 3& 6& 4\\ 4& 0& 8& 11& 2\end{array}\right]$$

Step 2: Column Reduction

Initialize $v_j=\min ({\text{col}}_j)$ and subtract from each column to ensure at least one zero per column. After this, we update our equality graph again—edges in this graph are where cost equals $u_i+v_j$ (i.e., zero entries).

Now for each column $j$, subtract the minimum value in that column from all entries in the column:

$$v_j=\underset{i}{\min }{C}_{ij}^{\prime }$$

This ensures each column also has at least one zero. Now, both rows and columns are guaranteed to have zeros, increasing the density of the equality graph and improving the chances of finding a perfect matching.

The resulting zero entries define edges in the equality graph. Only edges with zero reduced cost are part of this graph, and we attempt to find a matching within it.

$$v_j=\left[\begin{array}{ccccc}0& 0& 0& 0& 1\end{array}\right]⟶C^{\prime \prime }=C^{\prime }-v_j⟶C^{\prime \prime }=\left[\begin{array}{ccccc}4& 0& 3& 10& 2\\ 6& 14& 0& 4& 5\\ 0& 0& 2& 0& 0\\ 8& 0& 3& 6& 3\\ 4& 0& 8& 11& 1\end{array}\right]$$

At this point we have a zero-reduced matrix $C^{\prime \prime }$, and our current dual variables are:

• $u=[7,7,13,10,8]$
• $v=[0,0,0,0,1]$

We will now build a bipartite graph with an edge $(i,j)$ if $C_{ij}^{\prime \prime }=0$. This is our equality graph: the set of edges that satisfy $c_{ij}=u_i+v_j$.

Step 3: Initial Assignment (Matching)/Find A Maximum Matching In Equality Graph

Step 3.1 Row Based Assignment

Assign as many agents to tasks as feasible.

So scan each row. If there is exactly one zero, assign that agent to the corresponding task. Cross out all other zeros in the same column.

For each row I, if cell (I, j) is the only 0 valued cell available for assignment in that row, then assign xi,j = 1 (i.e. Agent I is matched to Task j for this iteration), and cross out all other 0 cells in column j.

If multiple 0s are available in any row, ignore that row

This greedily assigns unique matches and prevents conflicts. It reduces the size of the problem by locking in confident assignments.

We look for rows that contain exactly one zero (i.e., unique possible assignment) and tentatively assign:

• Row 1 ($i=1$): only zero is at $j=2$
  • Assign $(1,2)$
  • Cross out all other $0$‘s at column $j=2$ as column $j=2$ is assigned
• Row 2: only zero is at $j=3$
  • Assign $(2,3)$
• Row 3: multiple zeros, ignore.
• Row 4: only zero is at $j=2$, but already taken so skip
• Row 5: only zero is at $j=2$, but already taken so skip

Tentative matching results in:

$M=\{(1,2),(2,3)\}$

model the xij matrix here as well in math syntax

---

Now, scan each column. If there’s only one zero in a column, assign the task to that agent and cross out other zeros in the same row. This picks up more assignments missed in 3.1 and helps us get closer to a perfect matching.

Now apply the column-based assignment rule: For each column $j$, if there is exactly one zero (i.e., one possible assignment), assign that task to the corresponding agent.

step 3.2 –repeat step 3.1, but now for columns, instead of rows: Assign as many tasks to agents as feasible: For each column j, if cell (I, j) is the only 0 valued cell available in that column, then assign xi,j = 1 (i.e. Task j is matched to Agent I for this iteration), and cross out all other 0 cells in row I. If multiple 0s are available, ignore that column.

After both steps, we may still have unmatched rows or columns. If $|M|=N$, we are done.

Only consider rows/columns not already assigned or eliminated. From the reduced cost matrix:

With current assignments:

• Column 1 ($j=1$): only zero is at row $i=3$
  • Assign $(3,1)$
  • Cross out all other $0$‘s at row $i=3$
• Column 2: Already assigned, skip
• Column 3: Already assigned, skip
• Column 4: Only one zero at row $3$, but already taken so skip
• Column 5: Only one zer oat $i=3$ but already taken so skip

$M=\{(1,2),(2,3),(3,1)\}$

Caveat About Steps 3.1 And Steps 3.2

• After completion of step 3.2, a situation may arise that not ALL 0 valued cells in the matrix are crossed out or assigned.
• This indicates potentially multiple possible optimal matchings for the given problem.
• To ensure all zeros are crossed out or assigned after step 3.2, an approach is to break the impasse by
  • choosing an aribitrary assignment among the uncrossed 0s,
  • and repeating steps 3.1 and 3.2, until all 0 cells are crossed out or assigned.

Step 3.3

If $|M|<N$, we must improve the labeling to create more zero entries.

1. Mark all unassigned rows.

These rows indicate agents not yet matched. We begin our marking here.

2. If row is marked, for any 0 cell in that row, mark its corresponding column.

This explores the equality graph to find alternate paths or augmenting paths for matching.

3. For any marked column with an assignment (assigned zero), mark its corresponding row of that assignment.

This helps propagate markings to potentially find alternating paths or build towards the minimum vertex cover.

Repeat steps 3.3.2 and 3.3.3 until no new rows/columns can be marked.

4. Cover all unmarked rows and marked columns.

The number of covered row and columns represent the number of assignments in the reduced cost matrix.

This set of lines gives a minimum vertex cover in the equality graph, according to Kőnig’s theorem. The size of this cover equals the size of the maximum matching.

Step 4: Update Labeling & Cost Matrix

If |M| = N, (i.e. perfect matching reached), terminate the algorithm.

• The current M will be the optimal assignment, and current PN I=1 ui + PN j=1 vj value will be the min cost

else if |M| < N (i.e. perfect matching not yet reached), then

• Identify the minimum number $\theta$ among cells not covered.
• For every uncovered row, increase $u_i\leftarrow u_i+\theta$.
• For every covered column, decrease $v_j\leftarrow v_j-\theta$.

These updates preserve feasibility and increase the number of zero entries in the matrix, creating new edges in the equality graph.

Return to Step 3 and repeat until $|M|=N$ (i.e., a perfect matching is found).

Step 5: Repeat Matching

Once a perfect matching is found extract the assignment from the final matching $M$ and compute the total cost:

$$\text{Total cost}=\sum _{(i,j)\in M}{c}_{ij}$$

Or equivalently, since complementary slackness holds:

$$\text{Total cost}=\sum _{i=1}^5{u}_i+\sum _{j=1}^5{v}_j$$