Hungarian algorithm

The Hungarian algorithm finds a minimum-cost perfect matching in a weighted bipartite graph in polynomial time. It solves assignment problems by transforming costs and building a matching through augmenting paths.

Bipartite graph: A graph whose vertices split into two sets, with every edge joining vertices from opposite sets. The algorithm's assignments are edges between two disjoint groups.
Assignment problem: An optimization problem that pairs agents with tasks at minimum total cost, subject to one-to-one assignment constraints. The Hungarian algorithm is a specialized method for solving this problem.
Harold Kuhn: An American mathematician who introduced the Hungarian method for assignment problems in 1955. Kuhn named and developed the method from earlier Hungarian work.
Job scheduling: The allocation and ordering of jobs on workers or machines under specified objectives and constraints. Workers and jobs form the two sides of a common assignment instance.
Maximum-cardinality matching: A matching containing as many edges as possible, without regard to edge weights. The Hungarian algorithm optimizes cost among perfect matchings, rather than cardinality alone.
Perfect matching: A set of edges in a graph that touches every vertex exactly once. The algorithm's goal is a matching that assigns every item and recipient.
Weighted bipartite graph: A bipartite graph whose edges carry numerical weights or costs. Its edge costs encode the price of each possible assignment.
Dénes Kőnig: A Hungarian mathematician known for foundational results in graph theory, including theorems on bipartite graphs. Kőnig's work supplied one of the Hungarian method's mathematical foundations.
Multi-object tracking: The task of maintaining object identities across successive frames or sensor observations. Detection-to-track association can be formulated as a minimum-cost assignment.
Minimum-cost flow: A network optimization problem that sends required flow through edges at minimum total cost. It generalizes assignment to broader network structures and capacities.

Linked from 3 pages