What Is Optimal Matching?

Optimal matching is a combinatorial optimization problem concerned with finding a set of edges in a graph such that every selected edge shares no endpoint with another, and the total weight of the selected edges is maximized or the total cost is minimized. It belongs to the classical problems of combinatorial optimization and graph theory, drawing on linear programming, network flow theory, and polyhedral combinatorics. The problem arises naturally whenever discrete entities must be paired according to a cost or preference criterion, with a guarantee that the pairing is globally best rather than locally greedy.

The field draws intellectual lineage from the work of Jack Edmonds, whose 1965 paper on matching in non-bipartite graphs introduced the blossom algorithm and established that maximum matching can be solved in polynomial time. This result was foundational for the field of efficient combinatorial algorithms. Depending on whether the graph is bipartite or general, and whether edge weights are present, the problem takes distinct forms with different algorithmic solutions.

Bipartite Matching

In bipartite graphs, where vertices are divided into two disjoint sets and edges run only between them, the maximum cardinality matching problem is solved by augmenting-path algorithms such as the Hopcroft-Karp algorithm, which achieves O(sqrt(n) * m) time complexity. The weighted version, known as the assignment problem, seeks a perfect matching of minimum total weight and is solved by the Hungarian algorithm (also called the Kuhn-Munkres algorithm) in O(n^3) time. Bipartite matching underlies many scheduling and assignment tasks, such as assigning workers to jobs or matching medical residents to hospitals under the National Resident Matching Program, as analyzed in MIT's lecture notes on bipartite matching.

General Graph Matching

For non-bipartite graphs, the structure is more complex because odd cycles (blossoms) must be handled explicitly. Edmonds' blossom algorithm shrinks odd cycles into single nodes, allowing augmenting paths to be found correctly. The algorithm runs in O(n^3) in its basic form, with later implementations achieving O(n * m * alpha(n)), where alpha is the inverse Ackermann function. The Micali-Vazirani algorithm further improved the practical runtime. For the minimum-weight perfect matching problem on general graphs, the combination of the blossom technique with LP duality gives an exact polynomial-time algorithm, a result treated in detail in Combinatorial Optimization by Korte and Vygen.

Weighted and Online Variants

In the weighted matching setting, each edge carries a numerical weight and the goal is to find a matching of maximum total weight. The linear programming relaxation of this problem has an integer optimal solution for bipartite graphs (due to total unimodularity of the constraint matrix) but requires the blossom inequalities as cutting planes for general graphs. Online matching, where vertices on one side arrive sequentially and must be matched immediately, is relevant to internet advertising and cloud resource allocation; the RANKING algorithm by Karp, Vazirani, and Vazirani achieves a competitive ratio of 1-1/e, the best possible for adversarial inputs. Approximate matching under uncertainty is also studied through stochastic and robust optimization frameworks. The Stanford combinatorial optimization lecture notes give a thorough treatment of these variants.

Applications

Optimal matching has applications in a wide range of fields, including:

• Personnel and resource assignment, matching workers to tasks or shifts
• Medical residency placement and organ donor-recipient pairing
• Internet advertising, matching ads to queries in real-time bidding systems
• Network routing and load balancing
• Computer vision, where feature points between image pairs are matched geometrically
• Computational biology, aligning protein structures or genomic sequences