HungarianAlgorithmusVerfahren

The Hungarian algorithm is a classic method for solving the assignment problem in combinatorial optimization. Given an n-by-n cost matrix, it seeks a minimum-cost assignment that pairs each row with a unique column, so that every task is assigned to exactly one agent and every agent handles exactly one task. In graph terms, it finds a minimum-cost perfect matching in a bipartite graph.

History and naming: The algorithm was introduced by Harold W. Kuhn in 1955, building on earlier work related to the Hungarian method. It is often called the Hungarian algorithm, and in many texts it is referred to as the Kuhn–Munkres algorithm after later refinements by James Munkres. The names reflect its origins in Hungarian mathematical problem solving and its development in the mid-20th century.

How it works: The standard approach iterates through reductions and augmentations. First, subtract the smallest value in each row from every element in that row, then subtract the smallest value in each column from every element in that column, creating zeros. Next, attempt to cover all zeros with the minimum number of lines and find a feasible assignment among zeros. If a complete assignment is not yet possible, identify the smallest uncovered value, subtract it from all uncovered elements, and add it to all elements at the intersections of covering lines; repeat until a full assignment is obtained. The typical time complexity is O(n^3).

Variations and extensions: For maximization problems, costs can be transformed by negation or subtraction from a large constant. The algorithm extends to rectangular matrices by padding with dummy rows or columns to make the matrix square. It remains widely used in scheduling, workforce assignment, logistics, and other resource-allocation problems.

See also: assignment problem, bipartite matching, linear programming.