The Assignment Problem

You have the same number of workers and tasks, and each worker would cost a different amount to do each task. Assign one worker to each task — every worker busy, every task covered — so the total cost is as low as possible. Which pairing is best?

That's the assignment problem. It looks like it should be brutal: with n workers there are n! possible pairings, an explosion that dwarfs even the exponential blow-ups elsewhere on this site.

And yet — here's the twist, the same hopeful note as maximum flow — this one is easy. There's a fast, exact method that always finds the cheapest assignment. Sometimes the factorial monster is a paper tiger.

Try it. The grid shows what each worker costs on each task. Click a cell to assign that worker to that task — each worker gets exactly one task, and each task exactly one worker. Make the total cost as low as you can.

<p class="hint">{{hint}}</p>
<table id="grid"></table>
<p id="status" class="status"></p>
<div class="bar-btns">
  <button id="greedy" type="button">{{btn_greedy}}</button>
  <button id="opt" type="button">{{btn_optimal}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
table { border-collapse: collapse; margin: .3rem 0; }
th { font: 600 13px system-ui; color: #555; padding: .3rem .5rem; }
td { padding: 0; }
.cell { width: 56px; height: 48px; border: 1px solid #ddd; background: #fff; cursor: pointer; font: 700 16px ui-monospace, monospace; color: #333; transition: all .1s; }
.cell:hover { background: #f0f4f8; }
.cell.on { background: #2a9d8f; color: #fff; border-color: #2a9d8f; }
.status { font-size: 1rem; font-weight: 700; min-height: 1.3em; margin: .5rem 0; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c0392b; }
.bar-btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #457b9d; background: #457b9d; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #457b9d; }

// Code not found

Then compare. Greedy grabs the cheapest available cell, then the next — tempting, but it can lock in a bargain that forces an expensive pairing later. Optimal finds the true cheapest assignment. Watch greedy stumble where the optimal method never does.

Here's why this article is a breather:

• Checking an assignment is trivial: add the chosen costs.
• Brute force over all n! pairings is hopeless — even 20 workers give more permutations than atoms in your body.
• But it's in P. The Hungarian algorithm (Kuhn, 1955) finds the optimal assignment in $O(n^{3})$ — polynomial, exact, fast.
• It's a matching in disguise. The assignment problem is minimum-cost perfect matching on a bipartite graph, a special case of min-cost flow — which is why network ideas crack it.

So unlike knapsack or SAT, there's no wall here. The n! is an illusion; clever structure dissolves it.

Wherever you pair things one-to-one to minimize cost (or maximize value), it's the assignment problem:

• Ride-hailing and delivery: matching drivers to riders or orders to minimize wait and distance.
• Workforce: assigning staff to shifts or specialists to cases by skill and cost.
• Airlines and logistics: pairing crews with flights, trucks with routes.
• Sports and tournaments: assigning referees or scheduling matchups.
• Computer vision and tracking: matching detected objects between video frames.

Because the Hungarian algorithm is exact and fast, these systems get the provably best pairing in real time — no compromise needed.

The assignment problem wears the costume of a monster — n! possible pairings — and turns out to be a gentle one. The Hungarian algorithm solves it exactly and quickly, and greedy's stumbles only highlight how clever the right method is.

It's a valuable counterweight to the hard problems around it. A huge search space is a warning sign, not a verdict. Some problems that look impossible are simply waiting for the right idea — and once found, they become tools we lean on every day.