Hungarian - Kuhn–Munkres - Munkres Assignment-Algorithm

Explanation

- The **Hungarian Algorithm** (also known as the **Kuhn-Munkres Algorithm**) is a combinatorial optimization algorithm used for solving the **assignment problem**. Given a cost matrix, it finds the optimal way to assign `n` tasks to `n` workers such that the total cost is minimized.

-

• Steps

  • Subtract the row minima from each row.
  • Subtract the column minima from each column.
  • Cover zeros with a minimum number of horizontal and vertical lines.
  • Find the smallest uncovered number, subtract it from all uncovered elements, and add it to all covered elements.
  • Repeat until an optimal assignment is found.

• Time Complexity

  • Time complexity: O(n³), where n is the number of tasks (or workers).