The Problem
The Assignment Problem
The assignment problem asks for one job per worker at minimum total cost. A complete assignment is a permutation, so brute force grows quickly. The Hungarian method keeps the same optimum while reshaping the matrix into a form where the assignment is visible, which is the exact same one-to-one structure that later appears as a special transportation problem.
Cost matrix
There are 3 workers and 3 jobs. Why: an assignment must choose exactly one job for each worker and use each job exactly once. That one-to-one structure is what makes the problem different from choosing the cheapest cell in each row independently.
Permutation search
Brute force checks 6 permutations here. Why: each complete assignment is a different matching of workers to jobs. The count is small in the pinned example only because the matrix is small; factorial growth is the reason the method needs more than enumeration.
Target optimum
The optimum cost we will certify is 12. Why: the method should find the same minimum without enumerating every permutation. The important promise is not just a low number, but a certificate that the selected worker-job pairing is globally cheapest.
Diagram note
The table is the original cost data; highlighted reduction states come later. This is the input boundary: the costs are exact integers, and the assignment objective is to minimize their sum over a one-to-one matching. The reductions that follow preserve the optimal assignment exactly; they only change the bookkeeping scale. Pixel positions are rounded for layout; every number shown is exact.