Assignment Problem

Optimization · Axiom Academy

Optimal one-to-one matching with polynomial-time algorithms Given n workers and n tasks , with cost c ij for assigning worker i to task j, find a one-to-one matching that minimizes total cost. Each worker must be assigned to exactly one task Each task must be assigned to exactly one worker This creates a perfect matching in a bipartite graph 2. Linear Programming Formulation We can formulate the assignment problem as an integer program using binary decision variables x ij that equal 1 if worker i is assigned to task j, and 0 otherwise. Each row sums to 1 (each worker assigned once) Each column sums to 1 (each task assigned once) Variables must be binary: x ij ∈ 0, 1 The magic of the assignment problem: the constraint matrix has a special property called total unimodularity , which guarantees that the LP relaxation always yields integer solutions! Integer programs are generally NP-hard Linear programs can be solved in polynomial time Total unimodularity means we get the best of both worlds The constraint matrix has only entries from -1, 0, 1 The Hungarian algorithm (also called Kuhn-Munkres algorithm) solves the assignment problem in O(n³) time by iteratively improving a partial matching. Reduce costs: Subtract row/column minima to create zeros Find matching: Try to find a complete matching using only zero-cost edges Update potentials: If matching incomplete, adjust dual variables Repeat: Continue until perfect matching found 5. Bipartite Graph Visualization

This is the written version of the interactive lesson above. See the full Optimization course.