Introduction

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.

Match Them Up

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">Each cell is what that worker costs on that task. Click a cell to assign the worker to the task — one per row, one per column. Make the <b>total cost</b> as low as possible.</p>
<table id="grid"></table>
<p id="status" class="status"></p>
<div class="bar-btns">
  <button id="greedy" type="button">Greedy</button>
  <button id="opt" type="button">Optimal</button>
  <button id="reset" type="button" class="ghost">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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Assignment problem: pair each worker with one task at minimum total cost.
// n! pairings, yet solvable fast (Hungarian). Greedy (cheapest-first) can miss.
const COST = [[1, 2, 9], [3, 9, 9], [9, 9, 4]];
const N = COST.length;
const TASKS = ['T1', 'T2', 'T3'], WORKERS = ['W1', 'W2', 'W3'];
let assign = Array(N).fill(-1); // assign[row] = col

function permutations(arr) {
  if (arr.length <= 1) return [arr];
  const out = [];
  arr.forEach((v, i) => permutations(arr.slice(0, i).concat(arr.slice(i + 1))).forEach(p => out.push([v, ...p])));
  return out;
}
const OPT = Math.min(...permutations([...Array(N).keys()]).map(p => p.reduce((s, c, r) => s + COST[r][c], 0)));

function total() { let s = 0, n = 0; assign.forEach((c, r) => { if (c >= 0) { s += COST[r][c]; n++; } }); return { s, n }; }

function render() {
  const g = document.getElementById('grid');
  let html = '<tr><th></th>' + TASKS.map(t => `<th>${t}</th>`).join('') + '</tr>';
  for (let r = 0; r < N; r++) {
    html += `<tr><th>${WORKERS[r]}</th>` + COST[r].map((v, c) =>
      `<td><button class="cell${assign[r] === c ? ' on' : ''}" data-r="${r}" data-c="${c}">${v}</button></td>`).join('') + '</tr>';
  }
  g.innerHTML = html;
  g.querySelectorAll('.cell').forEach(b => b.addEventListener('click', () => {
    const r = +b.dataset.r, c = +b.dataset.c;
    if (assign[r] === c) { assign[r] = -1; }
    else { for (let r2 = 0; r2 < N; r2++) if (assign[r2] === c) assign[r2] = -1; assign[r] = c; }
    render();
  }));
  const { s, n } = total();
  const st = document.getElementById('status');
  if (n < N) { st.className = 'status'; st.textContent = fmt('Total: %s% (%n%/%N% assigned). The cheapest possible is %OPT%.', { s: s, n: n, N: N, OPT: OPT }); }
  else if (s <= OPT) { st.className = 'status ok'; st.textContent = fmt('Total cost %s% — that’s the cheapest possible! 🎉', { s: s }); }
  else { st.className = 'status bad'; st.textContent = fmt('Total cost %s%. The optimum is %OPT% — can you reach it?', { s: s, OPT: OPT }); }
}

function greedy() {
  assign = Array(N).fill(-1);
  const usedC = new Set(), usedR = new Set();
  const cells = [];
  for (let r = 0; r < N; r++) for (let c = 0; c < N; c++) cells.push({ r, c, v: COST[r][c] });
  cells.sort((a, b) => a.v - b.v);
  for (const { r, c } of cells) { if (!usedR.has(r) && !usedC.has(c)) { assign[r] = c; usedR.add(r); usedC.add(c); } }
  render();
  console.log(fmt('Greedy total %s% (optimal %OPT%).', { s: total().s, OPT: OPT }));
}
function optimal() {
  let best = null, bestCost = Infinity;
  for (const p of permutations([...Array(N).keys()])) { const cost = p.reduce((s, c, r) => s + COST[r][c], 0); if (cost < bestCost) { bestCost = cost; best = p; } }
  assign = [...best]; render();
}
document.getElementById('greedy').addEventListener('click', greedy);
document.getElementById('opt').addEventListener('click', optimal);
document.getElementById('reset').addEventListener('click', () => { assign = Array(N).fill(-1); render(); });
render();
Result
Console

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.

The Good News

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(n3)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.

Where It Matters

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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/assignment/Content licensed under CC BY-NC 4.0.