Family 4 · OR Problem Family
Assignment & Matching
Problems of mapping agents to positions bijectively or in many-to-one fashion, minimizing total cost or maximizing utility, where capacity is expressed as cardinality.
Linear Assignment Problem
Given an n × n cost matrix C, find a one-to-one assignment (permutation σ) of agents to tasks that minimizes the total cost ∑ ci,σ(i). The constraint matrix is totally unimodular, so the LP relaxation always yields integer solutions, making this one of the few integer programs solvable in polynomial time. The foundational problem in assignment theory with direct equivalence to minimum-weight perfect matching in bipartite graphs.
s.t. ∑j=1n xij = 1 ∀ i (each agent assigned once)
∑i=1n xij = 1 ∀ j (each task assigned once)
xij ∈ {0, 1}
| Algorithm | Type | Complexity | Reference |
|---|---|---|---|
| Hungarian (Kuhn-Munkres) | Exact | O(n³) | Kuhn (1955), Munkres (1957) |
| Auction Algorithm | Exact | O(n³) worst | Bertsekas (1988), parallelizable |
| Greedy Assignment | Heuristic | O(n²) | Assign cheapest available pair |
Generalized Assignment Problem
Extends the linear assignment problem by allowing agents to handle multiple tasks subject to capacity constraints. Each agent i has a capacity bi, and assigning task j to agent i consumes aij units of capacity at cost cij. The goal is to assign every task to exactly one agent while minimizing total cost and respecting agent capacities. NP-hard even for two agents, with applications in workforce scheduling, vehicle loading, and resource allocation.
s.t. ∑i=1m xij = 1 ∀ j (each task assigned once)
∑j=1n aij xij ≤ bi ∀ i (agent capacity)
xij ∈ {0, 1}
| Algorithm | Type | Complexity | Reference |
|---|---|---|---|
| Hungarian (Kuhn-Munkres) | Exact | O(n³) | Kuhn (1955), for LAP subproblem |
| Greedy Min-Cost | Heuristic | O(n²) | Iterative cheapest-pair assignment |
| Greedy Max-Regret | Heuristic | O(n² m) | Assign tasks with largest cost spread first |
Quadratic Assignment Problem
Assign n facilities to n locations to minimize the sum of products of flows between facilities and distances between their assigned locations. One of the hardest combinatorial optimization problems — no constant-factor approximation exists unless P = NP. The QAP generalizes the LAP: when the flow matrix F or distance matrix D is diagonal, it reduces to a linear assignment. Applications include hospital layout design, campus planning, keyboard optimization, and VLSI placement.
where π is a permutation of {1, ..., n}
Fij = flow between facilities i and j
Dkl = distance between locations k and l
| Algorithm | Type | Complexity | Reference |
|---|---|---|---|
| Branch & Bound | Exact | Exponential | Gilmore-Lawler bound, n ≤ 20 |
| Greedy QAP | Heuristic | O(n² log n) | Largest flow to shortest distance |
| Simulated Annealing | O(I · n) | Pairwise swap, Boltzmann acceptance |
Graph Matching
Select a subset M ⊆ E of pairwise non-adjacent edges in a graph G = (V, E) to maximize cardinality |M| or total weight ∑ we. For bipartite graphs, Hopcroft-Karp achieves O(√V · E) for cardinality matching and the Hungarian method yields O(V³) for weighted matching. For general (non-bipartite) graphs, Edmonds' blossom algorithm handles odd cycles by contraction. Konig's theorem establishes that in bipartite graphs, maximum matching equals minimum vertex cover.
s.t. ∀ v ∈ V: |{e ∈ M : v ∈ e}| ≤ 1 (each vertex matched at most once)
Perfect matching: |M| = |V| / 2 (every vertex matched)
Berge's theorem: M is maximum ⇔ no augmenting path exists
| Algorithm | Type | Complexity | Reference |
|---|---|---|---|
| Hopcroft-Karp (bipartite cardinality) | Exact | O(√V · E) | Hopcroft & Karp (1973) |
| Hungarian (bipartite weighted) | Exact | O(V³) | Kuhn (1955), Munkres (1957) |
| Edmonds' Blossom (general cardinality) | Exact | O(V · E) | Edmonds (1965) |
| Weighted Blossom (general weighted) | Exact | O(V³) | Edmonds (1965) |
| Gale-Shapley (stable matching) | Exact | O(V²) | Gale & Shapley (1962) |
Key References
Foundational works in assignment theory and graph matching
Linear Assignment
Kuhn, H.W. (1955). The Hungarian method for the assignment problem. Naval Research Logistics Quarterly, 2(1-2), 83–97.
Munkres, J. (1957). Algorithms for the assignment and transportation problems. SIAM Journal, 5(1), 32–38.
Jonker, R. & Volgenant, A. (1987). A shortest augmenting path algorithm for dense and sparse linear assignment problems. Computing, 38(4), 325–340.
Bertsekas, D.P. (1988). The auction algorithm: a distributed relaxation method. Annals of Operations Research, 14(1), 105–123.
Quadratic Assignment
Koopmans, T.C. & Beckmann, M. (1957). Assignment problems and the location of economic activities. Econometrica, 25(1), 53–76.
Sahni, S. & Gonzalez, T. (1976). P-complete approximation problems. JACM, 23(3), 555–565.
Taillard, E. (1991). Robust taboo search for the quadratic assignment problem. Parallel Computing, 17(4-5), 443–455.
Graph Matching
Edmonds, J. (1965). Paths, trees, and flowers. Canadian Journal of Mathematics, 17, 449–467.
Hopcroft, J.E. & Karp, R.M. (1973). An n5/2 algorithm for maximum matchings in bipartite graphs. SIAM Journal on Computing, 2(4), 225–231.
Gale, D. & Shapley, L.S. (1962). College admissions and the stability of marriage. American Mathematical Monthly, 69(1), 9–15.
Berge, C. (1957). Two theorems in graph theory. Proc. National Academy of Sciences, 43(9), 842–844.
Textbooks
Burkard, R.E., Dell'Amico, M. & Martello, S. (2009). Assignment Problems. SIAM.
Lovász, L. & Plummer, M.D. (1986). Matching Theory. North-Holland.
Explore the full repository with 57 problems across 10 families