Weighted Bipartite Matching

Weighted bipartite matching is the operations-research problem of finding, in a bipartite graph with two disjoint vertex sets U and V where every possible (u,v) edge carries a weight, the set of edges with maximum (or minimum) total weight, subject to no vertex touching more than one edge. It is the most general matching framework in combinatorial optimisation; special cases: the square and balanced case (|U| = |V|) is the **assignment problem**, solved by the Hungarian Method (Kuhn 1955; Munkres 1957) in polynomial time O(n³); the rectangular case (|U| ≠ |V|) is handled by dummy-vertex extension; the more general maximum-weight matching where unmatched vertices on either side are allowed has its own algorithmic family. Algorithms: weighted maximum matching is polynomial-time (Edmonds 1965 and later); the classical assignment case is solved by the Hungarian Method O(n³), and LAP (Jonker-Volgenant 1987) is faster in practice. Field applications: staff-task assignment, customer-technician matching, ad placement, online bipartite matching (#034), bid-bundle matching. Burkard, Dell'Amico and Martello (2009) is the canonical reference.