What is the Hungarian Method?

The Hungarian Method, also known as the Kuhn-Munkres algorithm, is a combinatorial optimization algorithm that solves the assignment problem in polynomial time. It is specifically designed to find the minimum cost (or maximum profit) when assigning a set of tasks to a set of resources (such as workers or machines) where each task must be assigned to exactly one resource.

How to Use This Calculator

Using our online Hungarian Method solver is simple and efficient. First, determine the size of your assignment problem (e.g., a 3x3 or 4x4 matrix). Enter the costs associated with each pairing in the input grid. Once the data is entered, click 'Solve Matrix'. The tool will process the steps of row reduction, column reduction, and zero covering to present the optimal assignment and the total minimum cost.

Steps in the Hungarian Algorithm

The process follows these core steps:

1. Row Reduction: Subtract the smallest element in each row from every element in that row.

2. Column Reduction: Subtract the smallest element in each column from every element in that column.

3. Covering Zeros: Cover all zeros in the resulting matrix with the minimum number of horizontal and vertical lines. If the number of lines equals N, an optimal assignment exists.

4. Iteration: If the number of lines is less than N, find the smallest uncovered element, subtract it from all uncovered elements, and add it to elements covered by two lines.

Frequently Asked Questions

Is the Hungarian Method only for minimization?
While primarily used for cost minimization, it can solve maximization problems by subtracting all values from the largest value in the matrix before starting.

What is an Assignment Problem?
An assignment problem is a special type of linear programming problem where the goal is to pair two sets of items optimally, often represented as a balanced square matrix.