Hungarian Algorithm

The Hungarian algorithm solves the linear assignment problem: given two sets of items and a cost for pairing each item in one set with each item in the other, it finds the one-to-one matching with the smallest total cost. Harold Kuhn published it in 1955 and named it after the Hungarian mathematicians Dénes Kőnig and Jenő Egerváry, whose earlier results it builds on; James Munkres analyzed it in 1957, so it is also called the Kuhn–Munkres algorithm. In computer vision it is the standard tool for matching detections to tracks in object tracking, predictions to ground truth when training set-based detectors, and results to annotations in evaluation.

Problem

Given $n$ workers, $n$ jobs, and a cost $c_{ij}$ for assigning worker $i$ to job $j$, assign each worker to exactly one job and each job to exactly one worker at minimal total cost. Equivalently, find a permutation $\sigma$ of $\{1, \ldots, n\}$ that minimizes

$$\sum_{i=1}^{n} c_{i \sigma(i)}.$$

This is a minimum-weight perfect matching in a complete bipartite graph. Trying all $n!$ permutations is infeasible beyond tiny $n$; the Hungarian algorithm takes polynomial time.

In tracking, the “workers” are tracks, the “jobs” are current detections, and the cost measures how poorly a detection fits a track.

Inputs and Outputs

Input: a cost matrix $C \in \mathbb{R}^{n \times m}$, where $c_{ij}$ is the cost of matching row item $i$ to column item $j$. To maximize a score such as IoU, negate it or use one minus the score.

Output: $\min(n, m)$ row–column pairs, with no row or column used twice, of minimal total cost. With gating (see below), some rows and columns may be left unmatched.

Intuition

Two observations drive the algorithm. First, subtracting a constant from an entire row or column does not change which assignment is optimal, because every complete assignment uses exactly one entry from each row and column, so all totals change by the same amount. Second, an assignment built entirely from zeros of a matrix with no negative entries is optimal, because no assignment can cost less than zero.

The algorithm therefore keeps reducing rows and columns, never creating negative entries, until enough zeros appear to form a complete assignment. The accumulated subtractions, called potentials, form a feasible solution of the linear-programming dual, and the zeros mark the pairs where the dual constraint is tight.

Algorithm

The classic matrix form, for a square cost matrix:

1. Row reduction. Subtract each row’s smallest entry from every entry in that row.
2. Column reduction. Do the same for each column. Every row and column now contains a zero.
3. Cover zeros with the minimum number of horizontal and vertical lines. By Kőnig’s theorem, this number equals the maximum number of zeros that can be selected with no two in the same row or column.
4. Test for optimality. If $n$ lines are needed, select $n$ independent zeros and stop.
5. Adjust. Otherwise, let $\delta$ be the smallest uncovered entry. Subtract $\delta$ from every uncovered entry and add it to every entry covered by two lines. This creates a new zero while keeping all entries non-negative. Return to step 3.

Modern implementations instead grow the matching one row at a time along a shortest augmenting path, which alternates between unmatched and matched pairs and enlarges the matching by one when flipped. Potentials keep reduced costs non-negative, so Dijkstra’s algorithm finds each path.

Mathematical Formulation

With $x_{ij} = 1$ if row $i$ is assigned to column $j$, the square assignment problem is the linear program

$$\min_{x} \sum_{i=1}^{n} \sum_{j=1}^{n} c_{ij} x_{ij} \quad \text{subject to} \quad \sum_{j=1}^{n} x_{ij} = 1 \;\; \forall i, \qquad \sum_{i=1}^{n} x_{ij} = 1 \;\; \forall j, \qquad x_{ij} \ge 0.$$

The constraint matrix is totally unimodular, so although the variables are relaxed from $\{0, 1\}$ to non-negative reals, the linear program always has an optimal solution with every $x_{ij}$ equal to 0 or 1. The dual assigns a potential $u_i$ to each row and $v_j$ to each column:

$$\max_{u, v} \sum_{i=1}^{n} u_i + \sum_{j=1}^{n} v_j \quad \text{subject to} \quad u_i + v_j \le c_{ij} \;\; \forall i, j.$$

The reduced cost of a pair is $\bar{c}_{ij} = c_{ij} - u_i - v_j \ge 0$; row and column reductions increase $u_i$ and $v_j$. By complementary slackness, a complete assignment using only pairs with $\bar{c}_{ij} = 0$ is optimal, and so are the potentials for the dual. The algorithm maintains dual feasibility and grows a matching on zero-reduced-cost pairs until it is complete.

Parameters

The assignment itself has no parameters; the modeling choices around it matter.

• Cost function. Distance between predicted and detected positions, one minus bounding-box overlap ($1 - \text{IoU}$), the Mahalanobis distance from a Kalman filter innovation, appearance-embedding distances, or weighted combinations.
• Gating threshold. The maximum cost at which a pair is still plausible.

Rectangular matrices and gating

Some tracks and detections should stay unmatched: a new object has no track, an occluded object no detection.

• Rectangular matrices. For an $n \times m$ matrix, every item on the smaller side is matched. Classic implementations pad with constant-cost dummy rows or columns; SciPy accepts rectangular input directly.
• Gating. Replace costs above the threshold with a very large value before solving, then discard any returned pair with that value. Filtering only after the solve is weaker: the solver may pair a track with a distant detection and push other tracks into worse matches to do so. A large finite value is safer than infinity, which some solvers reject when no complete assignment has finite cost.
• Explicit non-assignment costs. A more principled alternative builds an $(n + m) \times (m + n)$ matrix: the real costs, plus a dummy “unmatched” partner for each track and each detection at cost $\lambda$ (infeasible off the diagonals of those blocks), and zero cost for dummy–dummy pairs. A real pair is then chosen only when its cost is below the $2\lambda$ cost of leaving both items unmatched.

Complexity

The method as originally formulated runs in $O(n^4)$ time; Munkres (1957) showed that the number of steps is polynomially bounded. Tomizawa (1971) and, independently, Edmonds and Karp (1972) showed that augmenting along shortest paths while maintaining potentials gives $O(n^3)$, the bound of modern shortest-augmenting-path solvers such as Jonker–Volgenant. For a rectangular $n \times m$ matrix with $n \le m$, this approach takes $O(n^2 m)$ time. Memory is $O(nm)$.

Multi-object tracking produces small matrices, typically tens to a few hundred rows and columns per frame, which current solvers handle in about a millisecond or less; building the cost matrix usually costs more.

Implementation

SciPy’s linear_sum_assignment solves the rectangular problem with a modified Jonker–Volgenant shortest-augmenting-path method described by Crouse (2016), not the textbook matrix procedure. The example matches predicted track positions, such as those from a Kalman filter, to detections with a distance gate:

import numpy as np
from scipy.optimize import linear_sum_assignment

# Predicted positions of existing tracks (for example, from a Kalman filter).
tracks = np.array([[100.0, 120.0],
                   [300.0, 200.0],
                   [520.0,  80.0],
                   [ 60.0, 380.0]])
# Detections in the current frame.
detections = np.array([[305.0, 198.0],
                       [ 98.0, 125.0],
                       [700.0, 400.0],
                       [515.0,  90.0]])

# Cost: Euclidean distance between every track and every detection.
cost = np.linalg.norm(tracks[:, None, :] - detections[None, :, :], axis=2)

gate = 30.0                      # maximum plausible distance, in pixels
LARGE = 1e6                      # finite stand-in for "not allowed"
gated = np.where(cost > gate, LARGE, cost)

rows, cols = linear_sum_assignment(gated)
valid = gated[rows, cols] < LARGE
matches = list(zip(rows[valid].tolist(), cols[valid].tolist()))

unmatched_tracks = sorted(set(range(len(tracks))) - set(rows[valid].tolist()))
unmatched_detections = sorted(set(range(len(detections))) - set(cols[valid].tolist()))

print("matches (track, detection):", matches)
print("unmatched tracks:", unmatched_tracks)
print("unmatched detections:", unmatched_detections)
print("total cost:", round(cost[rows[valid], cols[valid]].sum(), 2))

Output:

matches (track, detection): [(0, 1), (1, 0), (2, 3)]
unmatched tracks: [3]
unmatched detections: [2]
total cost: 21.95

Without the gate, the square matrix forces a complete assignment, and the solver would also pair track 3 with detection 2, about 640 pixels away. With the gate, track 3 is reported as missed, a candidate for coasting on its prediction or deletion, and detection 2 as a candidate for a new track.

Properties and Behavior

• Exact and strongly polynomial. The result is globally optimal (ties are broken by the implementation), and running time depends only on matrix size, not cost magnitudes.
• Invariant to offsets and scaling. Adding a constant to a row or column, or scaling all costs by a positive constant, changes the optimal cost but not the optimal assignment.
• Sum of costs, not individual costs. It may accept a poor pair to allow two very good ones elsewhere, hence the need for an explicit gate.
• Dual certificate. No assignment costs less than the final dual bound $\sum_i u_i + \sum_j v_j$, which proves optimality.

Limitations

• One-to-one only. Merged detections, or several detections of one object, need a different formulation.
• Two sets, pairwise costs. Matching across three or more frames at once is a multidimensional assignment problem, NP-hard in general.
• Only as good as the costs. Poor motion predictions or weak appearance features produce confidently wrong matches, such as identity switches between crossing objects.
• Cubic scaling. For tens of thousands of items, $O(n^3)$ time and dense $O(n^2)$ memory become limiting, and sparse or approximate methods are preferred.

Uses in Computer Vision

In tracking-by-detection, each frame produces a cost matrix between the tracks’ predicted states and the current detections, and the assignment decides which detection updates which track. SORT, for instance, solves the assignment with the Hungarian algorithm on an IoU-based cost and rejects matches below a minimum overlap. Later trackers add appearance distances or run several assignment rounds for high- and low-confidence detections. Set-prediction detectors such as DETR match their fixed set of predictions to ground-truth objects during training, assigning unmatched predictions to a “no object” class; this one-to-one supervision removes the need for non-maximum suppression. In evaluation, multi-object tracking metrics such as MOTA, IDF1, and HOTA use optimal assignment to pair ground-truth objects with tracker output, whereas the COCO detection benchmark matches predictions to ground truth greedily in order of confidence.

Variants

Greedy matching. Accept pairs in order of increasing cost while their row and column are free. With a tight gate and well-separated objects it usually agrees with the optimal assignment; in crowded scenes it can force much worse matches.

Jonker–Volgenant (1987). Shortest augmenting paths with heuristic initialization: the same $O(n^3)$ worst case, but considerably faster in practice on dense problems; it underlies many modern solvers.

Auction algorithm. In Bertsekas’s auction algorithm, rows bid for columns, raising prices until every row is assigned. With a small enough bid increment it is optimal or near-optimal, and it suits sparse and parallel settings.

Min-cost flow. Assignment is a special case of minimum-cost network flow; some offline trackers formulate association over a whole video as a min-cost flow problem, with costs for starting and ending tracks.