3 Hungarian Algorithm

The Hungarian algorithm is presented as a classic way to solve the assignment problem: matching workers to tasks so that the total cost is minimized, or the total profit is maximized. The chapter frames this as a balanced case where the number of workers equals the number of tasks, which allows the problem to be represented as a square cost matrix. Rather than trying every possible pairing, which grows factorially and quickly becomes impractical, the algorithm reduces the problem to a structured sequence of matrix transformations that lead to an optimal one-to-one assignment.

The method is explained through step-by-step examples using row reduction, column reduction, and covering zeros with the fewest possible horizontal and vertical lines. If the number of lines equals the size of the matrix, an optimal assignment can be read from the zeros; if not, the matrix is adjusted by subtracting the smallest uncovered value from uncovered entries and adding it at line intersections, then the process repeats. This refinement exposes more usable zeros while preserving the relative costs, eventually making a full assignment possible. The chapter emphasizes how this approach transforms an explosion of possibilities into a polynomial-time procedure.

Beyond the worked examples, the chapter connects the algorithm to practical engineering uses such as airline crew scheduling and job allocation in distributed cloud systems, where costs may represent time, latency, resources, or operational constraints. It also notes that while the Hungarian algorithm is deterministic and optimal for one-to-one matching, real systems may require variations for unbalanced or dynamic workloads. Finally, it highlights the graph-theoretic view of the cost matrix as a bipartite graph, reinforcing the idea that the algorithm is a foundational tool for matching problems across many domains.

Cost matrix is created with the rows representing the workers and the columns representing the tasks. The values in the matrix denote the cost to complete the task. The cost can be replaced by other factors based on the use case like time taken, amount of work, or any other measurable value.

The circled values in the cost matrix are the minimum values in respective rows. Row reduction is performed, and each value in the row is subtracted from the minimum value in that row.

The squares in step 1 are the minimum in each column of the cost matrix after row reduction. These minimum values are used, and column reduction is performed. The column Floors is only modified and subtracted by 1.

In our step 3, we start drawing lines across the rows and columns that contain 0. Lines across column 0, column 2, and row 1 cover all the zeroes.

The cost matrix consists of four developers from 0 to 3 and four modules, Mod 0 to Mod 3. The values within the matrix represent the number of hours required for the developer to complete the module.

The circled numbers in the matrix are the lowest values in each row to be subtracted across the row. The row reduction is performed and shown in the step 1 as the modified matrix.

The marked square boxes in step 1 are the lowest value in each column to perform column reduction. The values are subtracted across each column and the resultant modified matrix is shown in step 2.

Lines are drawn across the matrix in step 3, covering column 0, column 2, and row 2. But only 3 lines are drawn to cover all zeros and do not match the total developer value of 4. A 1-1 assignment is not possible at this stage.

The dotted box in step 3 is the value of the smallest number uncovered. This number is subtracted from all the uncovered values. The same value is added to the intersection of the lines i.e. is [2,0] and [2,2]. The lines are drawn again covering row 0, row 2, and column 2. The lines still are still 3 and do not equal to the number of developers which is 4.

The same step is repeated again. The dotted box in step 4, is the smallest uncovered value. This value is subtracted from the matrix and added to the intersection at [0,2] and [2,2]. The lines are drawn again across column 0, column 2, column 3, and row 2. The lines equal 4 now, and a 1-1 assignment is possible.

The bipartite graph shows two sets, U and V. Every edge from the vertex (Alice, Bob, Carol) is connected to another set V vertices (Kitchen, Floors, Windows) with the value of the edge as the costs.

• The Hungarian algorithm is an allocation problem to map an equal number of workers to tasks. The objective is to minimize the cost to obtain the optimal mapping.
• If the algorithm is not used, then manual combinations yield factorial time complexity. At enterprise scale, with 100 workers and 100 tasks, this creates an incomputable number of combinations.
• The cost matrix is created where the rows are the workers and the columns are the tasks. With the implementation of the Hungarian algorithm, the time complexity reduces to O(n3) from the factorial O(n!).
• The algorithm performs row reduction and column reduction. The algorithm subtracts the minimum value from every row, followed by subtracting the minimum value from every column. This safely alters the relative weights to expose zero-cost assignment opportunities.
• To verify if a complete assignment is possible, the algorithm requires drawing the absolute minimum number of straight lines to cover all zeroes in the matrix. If the minimum lines equal n, an optimal state is reached.
• If the lines drawn are strictly less than n, the matrix is bottlenecked. The algorithm forces a mathematical shift by locating the smallest uncovered number, subtracting it from all uncovered cells, and adding it to any cell where two lines intersect. This process loops until the lines equal n.
• Once the optimal state is achieved, assignments are locked in by selecting independent zeroes (starting with rows/columns that only possess a single zero). These mappings are cross-referenced with the initial cost matrix to calculate the final minimum cost.
• Real-world applications like crew scheduling use the Hungarian algorithm for the assignment of crew and staff to related tasks. Job scheduling in distributed systems is another application to map the incoming jobs or requests to physical servers.

1. Harold W. Kuhn, "The Hungarian Method for the assignment problem", Naval Research Logistics Quarterly, 2: 83–97, 1953. Kuhn's original publication.
2. YouTube -https://youtu.be/aocsXmWwAZQ?si=SFakJwJVqDFkJwUa
3. Algorithm in action -https://www.hungarianalgorithm.com/solve.php

FAQ