Assignment problem

The assignment problem is a fundamental problem in combinatorial optimization concerning the minimum-cost pairing of two finite sets. In its standard form, an equal number of agents and tasks are given, together with a numerical cost for assigning each agent to each task. A feasible assignment pairs every agent with exactly one task and every task with exactly one agent. The objective is to minimize the sum of the costs associated with the selected pairings.

The problem is also called the linear assignment problem because both its objective function and its constraints admit a linear programming formulation. Despite being naturally expressed with binary decision variables, its standard formulation can be solved through linear programming without separately imposing integrality. This property follows from the structure of the constraint matrix and connects the problem with bipartite matching, network flow, and the geometry of doubly stochastic matrices.

Mathematical formulation

Let (A={1,\ldots,n}) be a set of agents and (T={1,\ldots,n}) a set of tasks. For every pair ((i,j)\in A\times T), let (c_{ij}) denote the cost of assigning agent (i) to task (j). Introducing a variable (x_{ij}), with (x_{ij}=1) when that pairing is selected and (x_{ij}=0) otherwise, gives the integer program

[ \begin{aligned} \text{minimize}\quad & \sum_{i=1}^{n}\sum_{j=1}^{n} c_{ij}x_{ij},\ \text{subject to}\quad & \sum_{j=1}^{n}x_{ij}=1 && \text{for every }i,\ & \sum_{i=1}^{n}x_{ij}=1 && \text{for every }j,\ & x_{ij}\in{0,1}. \end{aligned} ]

Each feasible solution corresponds to a permutation (\pi) of the tasks, and its cost is

[ \sum_{i=1}^{n} c_{i,\pi(i)}. ]

The number of feasible assignments is (n!), so direct enumeration grows too rapidly for large instances. The algebraic structure of the constraints nevertheless permits algorithms whose running times are polynomial in (n).

A rectangular instance contains (m) agents and (n) tasks. Depending on the model, every member of the smaller set is matched while some members of the larger set remain unmatched. Such an instance can be converted into a square one by introducing dummy agents or dummy tasks with costs representing nonassignment. This transformation preserves the basic matching structure but changes the interpretation of feasibility when nonassignment itself carries a cost.

Graph interpretation

The assignment problem is equivalent to finding a minimum-weight perfect matching in a complete bipartite graph. One side of the graph represents agents, while the other represents tasks. The edge between agent (i) and task (j) has weight (c_{ij}), and a perfect matching selects one incident edge at every vertex.

This interpretation extends naturally to incomplete assignment graphs. A forbidden pairing is represented by the absence of its edge rather than by a finite cost. A feasible complete assignment then exists precisely when the graph has a perfect matching, as characterized by Hall's marriage theorem. When no perfect matching exists, the optimization problem is infeasible rather than merely expensive.

The same problem can be represented as a minimum-cost flow instance. A source is connected to every agent, each agent is connected to the admissible tasks, and every task is connected to a sink. Unit capacities enforce one-to-one pairing, while edge costs encode assignment costs. The integrality theorem for network flows guarantees an integral optimum when all capacities are integral.

Linear programming structure

Relaxing the binary restrictions to (x_{ij}\geq 0) produces

[ \begin{aligned} \text{minimize}\quad & \sum_{i,j} c_{ij}x_{ij},\ \text{subject to}\quad & \sum_j x_{ij}=1,\ & \sum_i x_{ij}=1,\ & x_{ij}\geq 0. \end{aligned} ]

The feasible region is the Birkhoff polytope, whose points are doubly stochastic matrices. The Birkhoff–von Neumann theorem states that every doubly stochastic matrix is a convex combination of permutation matrices. Consequently, every extreme point of the feasible region is integral, and a linear objective attains an optimum at a permutation matrix.

The same conclusion follows from total unimodularity. After one redundant equality is removed, the constraint matrix is an incidence matrix of a bipartite graph and is totally unimodular. An integral right-hand side therefore yields integral vertices in the associated polyhedron.

The dual linear program assigns a potential (u_i) to every agent and a potential (v_j) to every task:

[ \begin{aligned} \text{maximize}\quad & \sum_i u_i+\sum_j v_j,\ \text{subject to}\quad & u_i+v_j\leq c_{ij} && \text{for every }i,j. \end{aligned} ]

The quantity (c_{ij}-u_i-v_j) is the reduced cost of the pairing ((i,j)). By complementary slackness, every edge selected in an optimal assignment has zero reduced cost under an appropriate optimal dual solution. Primal–dual algorithms exploit this relation by alternating between changes to the potentials and augmentations of a matching formed from zero-reduced-cost edges.

Historical development

Early forms of the problem arose from the study of transportation and optimal spatial pairing. In 1781, Gaspard Monge formulated a continuous transportation problem involving the movement of material between distributions. The modern discrete assignment problem is narrower, but it retains Monge's central concern with selecting pairings that minimize aggregate cost. Cost matrices satisfying a Monge array inequality preserve a distinct connection to this origin and admit algorithms specialized to their ordered structure.

During the nineteenth century, Carl Gustav Jacob Jacobi examined a combinatorial optimization procedure in connection with systems of differential equations. His treatment anticipated several features later associated with the assignment problem, including transformations of a numerical matrix that preserve the set of optimal permutations.

The decisive graph-theoretic foundations appeared in the early twentieth century. Dénes Kőnig established results relating matchings and vertex covers in bipartite graphs, while Jenő Egerváry developed a weighted generalization that supplied the dual structure required for optimization. Their work provided the mathematical basis for the method later named after the Hungarian mathematical tradition.

In 1955, Harold Kuhn presented the Hungarian algorithm as a systematic procedure for the assignment problem and explicitly connected it with the results of Kőnig and Egerváry. Kuhn's formulation made the primal–dual structure operational through reductions of the cost matrix, construction of zero-cost matchings, and updates based on minimum vertex covers.

A 1957 analysis by James Munkres and You Watanabe gave a finite implementation of the method in which the number of elementary operations was bounded by a polynomial in the matrix dimension and was independent of the numerical magnitudes of the costs. Their formulation also clarified the correspondence between matrix reductions and changes in feasible dual potentials. This version became widely associated with the name Kuhn–Munkres algorithm, although the underlying mathematical components originated across the earlier results.

Subsequent work by Jack Edmonds, Richard Karp, and Nobuaki Tomizawa refined the organization of augmenting paths and potential updates. These developments yielded implementations with (O(n^3)) running time for dense (n\times n) cost matrices.

Algorithms

The Hungarian algorithm maintains a feasible set of dual potentials and a matching consisting of edges whose reduced costs are zero. If the zero-reduced-cost graph contains a perfect matching, complementary slackness establishes optimality. Otherwise, an alternating-tree search identifies vertices reachable from unmatched agents, after which the dual potentials change by the smallest amount that creates an additional zero-reduced-cost edge without violating dual feasibility.

With suitable data structures, the dense form of the algorithm runs in (O(n^3)) time and uses (O(n^2)) storage for an explicitly represented cost matrix. Sparse instances can instead be treated through weighted bipartite matching or minimum-cost flow algorithms that avoid materializing absent edges.

The successive shortest path algorithm interprets assignment as unit-capacity minimum-cost flow. Each augmentation sends one unit of flow through a least-cost residual path, while vertex potentials permit the use of nonnegative reduced costs. Its behavior closely parallels augmenting-path versions of the Hungarian method, although the flow formulation extends directly to capacities greater than one.

The auction algorithm, introduced by Dimitri Bertsekas, uses a price for each task and assigns agents through competitive bidding. Its approximate complementary-slackness condition is governed by a parameter (\varepsilon). For integral costs, sufficiently small (\varepsilon) yields an exact optimum, while scaling variants reduce the dependence on the range of the numerical costs.

Variants and boundaries

The maximum-weight assignment problem differs only in the direction of optimization. It is equivalent to the minimum-cost form after an affine transformation of the edge weights. Negative costs do not change the combinatorial structure, because adding a constant to every entry of a row or column shifts the cost of every feasible assignment by the same amount.

The bottleneck assignment problem minimizes the largest selected cost rather than the sum of all selected costs. Its objective is therefore not the linear objective of the standard assignment problem, even though its feasible solutions are the same perfect matchings. It can be analyzed through threshold graphs in which an edge is retained only when its cost does not exceed a specified bound.

The quadratic assignment problem includes interactions between pairs of assignments. Its objective depends on products such as (x_{ij}x_{k\ell}), commonly representing flows between facilities and distances between locations. This change removes the linear matching structure and produces a substantially different computational problem that is NP-hard.

The generalized assignment problem permits each agent to receive multiple tasks subject to a capacity constraint. Task consumption can vary across agents, so the resulting model combines assignment decisions with knapsack problem structure. Its feasible region no longer has the integral polyhedral description of the one-to-one assignment problem.

Interpretation and applications

An assignment cost need not represent a monetary expenditure. It can encode elapsed time, geometric distance, expected loss, or the negative of a compatibility score. The linear model requires the total value of an assignment to equal the sum of values attached independently to the selected pairs. Interactions among assignments fall outside this assumption and require a different optimization model.

In labor allocation, agents represent workers and tasks represent positions, with costs derived from completion times or mismatch penalties. In data association, detected observations are paired with predicted objects according to statistical discrepancy. In computational geometry, finite point sets are paired under a distance-based objective. These uses share the same optimization structure even though the interpretation of an edge weight differs among domains.