Skip to main content

Understanding the Hungarian Matching Algorithm

What Does It Solve?

The Hungarian Matching Algorithm solves the assignment problem:

“How do we assign n tasks to n agents such that the total cost is minimized (or total profit is maximized)?”

Think of it like:

  • Assigning jobs to workers
  • Matching predicted boxes to GT boxes
  • Matching students to schools optimally

Example Problem

We have 3 workers and 3 jobs. Each cell in the cost matrix shows how much it costs to assign a worker to a job.

Cost Matrix:
          Job1 Job2 Job3
Worker1    9     2     7
Worker2    6     4     3
Worker3    5     8     1

We want to assign each worker to one job so that the total cost is minimized.

Algorithm Intuition

The Hungarian algorithm operates in phases:

[1] Subtract Row Minimums     → Make sure each row has a zero
[2] Subtract Column Minimums  → Ensure each column has a zero
[3] Star Zeros                → Mark independent zeros (no overlap in row/column)
[4] Cover Columns with Stars  → Try to cover all assignments
[5] If not optimal:
    ↓ Find and prime new zeros
    ↓ Update covers and create alternating paths
    ↓ Adjust matrix (add/subtract smallest uncovered value)
Repeat until all rows assigned

Pseudocode Breakdown

Here’s the pseudocode logic:

Input: cost_matrix[n][n]

1. For each row, subtract the minimum value from each element in the row
2. For each column, subtract the minimum value from each element in the column

3. Star zeros:
   - For each zero, if its row and column are not covered, star it
   - Cover the row and column temporarily

4. Cover columns with stars
   - If all columns are covered, we're done
   - Else, go to step 5

5. While not all columns are covered:
   a. Find an uncovered zero, prime it
   b. If there is no starred zero in the same row:
       - Construct alternating path of stars and primes
       - Unstar stars, star primes along the path
       - Clear covers, go back to step 4
   c. Else:
       - Cover the row, uncover the column of the star
       - Repeat search

6. If no uncovered zeros:
   - Find the smallest uncovered value
   - Subtract it from all uncovered elements
   - Add it to elements covered twice
   - Go back to step 5

Step-by-Step Example

Let’s apply the Hungarian Algorithm to this matrix:

[9, 2, 7]
[6, 4, 3]
[5, 8, 1]

Subtract row mins:

Row mins = [2, 3, 1]
Result:
[7, 0, 5]
[3, 1, 0]
[4, 7, 0]

Subtract column mins:

Column mins = [3, 0, 0]
Result:
[4, 0, 5]
[0, 1, 0]
[1, 7, 0]

Star non-overlapping zeros:

[4, *0, 5]
[*0, 1, 0] ← overlapping
[1, 7, *0]

Final stars:
(0,1), (1,0), (2,2)

→ Covered columns = 3 → All matched!

References

  1. Hungarian Algorithm (Wikipedia): https://en.wikipedia.org/wiki/Hungarian_algorithm
  2. Hungarian Algorithm Illustrated: https://brc2.com/the-algorithm-workshop/


Tags

Comments

Post a Comment

Popular

Understanding SentencePiece: A Language-Independent Tokenizer for AI Engineers

In the realm of Natural Language Processing (NLP), tokenization plays a pivotal role in preparing text data for machine learning models. Traditional tokenization methods often rely on language-specific rules and pre-tokenized inputs, which can be limiting when dealing with diverse languages and scripts. Enter SentencePiece—a language-independent tokenizer and detokenizer designed to address these challenges and streamline the preprocessing pipeline for neural text processing systems. What is SentencePiece? SentencePiece is an open-source tokenizer and detokenizer developed by Google, tailored for neural-based text processing tasks such as Neural Machine Translation (NMT). Unlike conventional tokenizers that depend on whitespace and language-specific rules, SentencePiece treats the input text as a raw byte sequence, enabling it to process languages without explicit word boundaries, such as Japanese, Chinese, and Korean. This approach allows SentencePiece to train subword models di...
Post a Comment
Read more

Mastering the Byte Pair Encoding (BPE) Tokenizer for NLP and LLMs

Byte Pair Encoding (BPE) is one of the most important and widely adopted subword tokenization algorithms in modern Natural Language Processing (NLP), especially in training Large Language Models (LLMs) like GPT. This guide provides a deep technical dive into how BPE works, compares it with other tokenizers like WordPiece and SentencePiece, and explains its practical implementation with Python code. This article is optimized for AI engineers building real-world models and systems. 1. What is Byte Pair Encoding? BPE was originally introduced as a data compression algorithm by Gage in 1994. It replaces the most frequent pair of bytes in a sequence with a single, unused byte. In 2015, Sennrich et al. adapted BPE for NLP to address the out-of-vocabulary (OOV) problem in neural machine translation. Instead of working with full words, BPE decomposes them into subword units that can be recombined to represent rare or unseen words. 2. Why Tokenization Matters in LLMs Tokenization is th...
Post a Comment
Read more

ZeRO: Deep Memory Optimization for Training Trillion-Parameter Models

In 2020, Microsoft researchers introduced ZeRO (Zero Redundancy Optimizer) via their paper "ZeRO: Memory Optimization Towards Training Trillion Parameter Models" (arXiv:1910.02054). ZeRO is a memory optimization technique that eliminates redundancy in distributed training, enabling efficient scaling to trillion-parameter models. This provides an in-depth technical breakdown of ZeRO's partitioning strategies, memory usage analysis, and integration with DeepSpeed. 1. What is ZeRO? ZeRO eliminates redundant memory copies of model states across GPUs. Instead of replicating parameters, gradients, and optimizer states across each GPU, ZeRO partitions them across all devices. This results in near-linear memory savings as the number of GPUs increases. 2. Limitations of Traditional Data Parallelism In standard data-parallel training, every GPU maintains: Model Parameters $\theta$ Gradients $\nabla \theta$ Optimizer States $O(\theta)$ This causes memory usage ...
Post a Comment
Read more