KuhnMunkres

Kuhn–Munkres algorithm, often called the Hungarian algorithm, is a classical method for solving the assignment problem. Given a matrix of weights representing profit or cost for assigning n workers to n tasks, the goal is to find a one-to-one assignment that maximizes total weight (or minimizes total cost). The algorithm computes a maximum weight matching in a complete bipartite graph or equivalently a permutation that maximizes the sum of selected weights. It is most efficient for square matrices, though rectangular instances may be reduced by padding.

Historically, Harold W. Kuhn introduced the method in 1955 to find maximum matchings in bipartite graphs; James Munkres generalized and refined the approach for the weighted assignment problem, publishing in 1957. Due to these developments, the method is frequently named Kuhn–Munkres. In many contexts it is also called the Hungarian algorithm, after the 1950s work of Kuhn and of the later Hungarian method.

The approach uses dual variables (labels) on the two partition sides and maintains an equality (zero reduced-cost) subgraph. It iteratively searches for augmenting paths within this subgraph to increase the total weight. When no augmenting path exists, the algorithm adjusts the labels to create new zero-reduced-cost edges, enlarging the equality graph and continuing until a perfect matching is found. The standard implementation runs in O(n^3) time for an n×n instance and can be adapted to rectangular matrices by padding with dummy rows or columns.

Applications include task assignment, scheduling, resource allocation, and data association in computer vision, as well as various optimization problems in operations research.