What is the assignment problem?

The assignment problem is a classic combinatorial optimization problem: given a set of workers and tasks, each with an associated cost, find the one-to-one pairing that minimizes the total cost. It appears naturally in scheduling, logistics, resource allocation, and operations research — any situation where you need to match two groups in the most efficient way possible.

The problem is solved with the Hungarian algorithm (also called the Munkres algorithm), an efficient method developed in the 1950s. Unlike brute-force approaches that must evaluate every permutation, the Hungarian algorithm finds the optimal solution in polynomial time, making it practical even for moderately large matrices.

Tool description

Enter a cost matrix representing how much it costs to assign each worker to each task, then click Solve to instantly find the optimal assignment. The tool highlights which worker-task pairs minimize total cost and displays the result in a clear table alongside the optimal total cost.

Examples

Input matrix (3 workers × 3 tasks):

Task 1 Task 2 Task 3
Worker 1 400 150 400
Worker 2 400 450 600
Worker 3 300 225 300

Optimal assignments:

Worker Task Cost
Worker 1 Task 2 150
Worker 2 Task 1 400
Worker 3 Task 3 300

Total cost: 850

Features

  • Editable matrix — click any cell or column header to rename workers, tasks, and costs directly in the table
  • Configurable size — supports matrices from 2×2 up to 8×8
  • Instant results — the Hungarian algorithm runs in-browser with no server round-trip

How it works

The tool uses the Munkres (Hungarian) algorithm to solve the assignment problem optimally. It constructs a cost matrix from your inputs, applies a series of row and column reduction steps, and iteratively finds a maximum matching of zeros until a complete optimal assignment is identified. The time complexity is $O(n^3)$, where $n$ is the matrix dimension.

For non-square matrices (more workers than tasks or vice versa), the algorithm pads the matrix with zeros so that every worker and every task is matched.

Options explained

  • Number of workers / rows — controls how many rows appear in the cost matrix (2–8)
  • Number of tasks / columns — controls how many columns appear in the cost matrix (2–8)
  • Cost matrix cells — enter the cost of assigning a specific worker to a specific task; any numeric value is accepted

Limitations

  • Matrix size is capped at 8×8 (64 cells)
  • The algorithm minimizes total cost; to maximize (e.g., for profit matrices), negate the values before entering them
  • Non-numeric cell values are treated as zero