Introduction

The Hungarian algorithm, also known as the Kuhn-Munkres algorithm, is a combinatorial optimization algorithm that solves the assignment problem. The classic assignment problem aims to match `n` workers to `n` jobs such that the total cost is minimized, given the cost of assigning each worker to each job. The problem is typically visualized as a cost matrix where the goal is to find the minimum cost assignment.

However, in practical scenarios, the requirement often extends to assigning multiple jobs per worker. This article delves into the adaptations necessary for this scenario, explaining the algorithm's mechanics, enhancements, and applications where multiple jobs need assignment per worker.

Background

Classic Assignment Problem

The classic assignment problem can be mathematically represented with a cost matrix, `C`, where `C[i][j]` is the cost of assigning worker `i` to job `j`. The objective is to find a perfect matching with minimum total cost. The Hungarian algorithm finds such an assignment by transforming the cost matrix into a matrix where the minimum number of zeroes covers all cells.

Assignment Problem with Multiple Jobs

In scenarios where workers can handle more than one job, the algorithm must be adapted. Here, the problem is known as a multi-agent assignment problem or multi-task assignment. Instead of a perfect one-to-one match, the goal is to assign `m` jobs to `n` workers (where typically `m > n`), such that the sum of the assignment costs is minimized, and each worker can be assigned multiple jobs.

Algorithmic Foundation

Key Concepts

• Cost Matrix: A matrix defining the cost of assigning each worker to each job.
• Zero-Cover: A set of lines that cover all zeroes in the modified cost matrix.
• Reduced Matrix: The intermediate matrix obtained by subtracting row and column minima.

Hungarian Algorithm for Multiple Jobs

1. Expand the Cost Matrix: For the multiple-job version, the cost matrix may need to be expanded if there's a significant imbalance between jobs and workers, adding dummy workers to balance dimensions.
2. Initialization: Start by modifying the cost matrix to create as many zeroes as possible. This is done by subtracting the row minima and then the column minima.
3. Cover Zeroes with Minimal Number of Lines: Use the zero-covering method to cover all the zeroes in the cost matrix with a minimum number of lines (rows and/or columns).
4. Adjust the Matrix:
   • Identify the smallest non-covered element.
   • Subtract this smallest value from every uncovered element.
   • Add it to elements covered twice, ensuring new zeroes are created.
5. Iterate: Repeat covering and adjusting until an optimal assignment is feasible.
6. Assignment: Assign jobs to workers by choosing an optimal arrangement of zeroes, ensuring each worker assignment does not exceed their capacity.

Example

Consider a situation with 3 workers and 5 jobs:

• Efficiency: Works in polynomial time, specifically $O(n^3)$, making it suitable for large datasets.
• Optimality: Guarantees an optimal solution, minimizing maximum costs.
• Scalability: In scenarios with drastically mismatched jobs and workers, the matrix expansion could lead to computational inefficiency.
• Complexity for Capacities: Requires tuning to handle worker capacity constraints, especially for various practical adaptations.