Overview of Kuhn-Munkers algorithm and example implementation

📘 Overview of the Kuhn–Munkres Algorithm (Hungarian Method)

The Kuhn–Munkres algorithm, also known as the Hungarian Algorithm, is an efficient method for solving the assignment problem, which involves finding the minimum (or maximum) weight perfect matching in a weighted bipartite graph.

This algorithm aims to match nodes from two disjoint sets—typically U (e.g., workers) and V (e.g., tasks)—in a one-to-one fashion, minimizing the total cost (or maximizing the total gain) of the assignments. The assignment problem frequently arises in real-world situations such as resource allocation, job-task assignment, and scheduling.

Each edge in the bipartite graph is associated with a cost (or profit), and the goal is to find a perfect matching between elements in sets U and V that minimizes the total cost (or maximizes total gain).

Main Steps of the Hungarian Algorithm

1. Row Reduction
   Subtract the minimum value of each row from all elements in that row. This ensures that each row contains at least one zero.

2. Column Reduction
   Similarly, subtract the minimum value of each column from all elements in that column. This increases the number of zero entries (potential match candidates).

3. Zero Coverage (Line Covering Step)
   Cover all zeros in the matrix using the minimum number of horizontal or vertical lines.

4. Optimality Check
   If the number of covering lines equals the number of rows/columns (n), an optimal assignment has been found.

5. Adjustment Step (if needed)
   If fewer than n lines are used, find the smallest uncovered value in the matrix. Subtract it from all uncovered elements and add it to elements at intersections of lines. Repeat from Step 3.

Through these steps, the algorithm converges to the optimal assignment with minimum cost. This sequence of operations forms the core of the Hungarian method.

Time Complexity

• The time complexity of the Hungarian Algorithm is O(n³), where n is the number of workers or tasks.

• As the problem size increases, computational time scales cubically. Thus, the algorithm is well-suited for small to medium-sized problems. For larger instances, optimizations or approximation algorithms may be necessary.

Mathematical Formulation

The assignment problem can be formulated as a minimization problem:

$$\underset{X}{\min }\sum _{i=1}^n\sum _{j=1}^n{C}_{i,j}\cdot X_{i,j}$$

Subject to the constraints that each worker is assigned to exactly one task, and each task is assigned to exactly one worker. Here,

$X_{i,j}\in \{0,1\}$

Xi,j​∈{0,1} indicates whether worker i is assigned to task j.

Implementations in Major Languages

• Python:

  • scipy.optimize.linear_sum_assignment() provides a fast, reliable implementation of the Hungarian Algorithm.

  • Input: Cost matrix → Output: Optimal assignment with minimum cost.

• C++:

  • Numerous implementations exist, often used in competitive programming.

  • Common function names: km_match(), blossom(), etc.

• JavaScript:

  • hungarian-algorithm is a lightweight npm package available for both browser and Node.js environments.

Summary

The Hungarian Algorithm is a cornerstone solution for the assignment problem, with wide applicability across domains like operations research, computer vision, education, and logistics. Its availability in multiple programming languages and libraries makes it easy to integrate into practical systems.

Let me know if you’d like visual diagrams, code examples, or specific domain applications such as education, factory scheduling, NLP, or image processing.

Related Algorithms to the Kuhn–Munkres Algorithm

The Kuhn–Munkres algorithm (Hungarian method) lies at the intersection of matching problems, optimization, and network flow. Below is a structured categorization of algorithms related to it:

1. Matching Algorithms

2. Maximum Flow & Minimum-Cost Flow Algorithms

Kuhn–Munkres can be viewed as a specialized form of the minimum-cost flow problem under the constraints of a complete bipartite graph with one-to-one matching.

3. Stable Matching Algorithms (Different Objective)

These algorithms are related by matching but aim for stability, not cost minimization. Thus, their goal differs from that of Kuhn–Munkres.

4. Other Assignment Algorithms

Summary Table

Practical Implementation Example of the Kuhn–Munkres Algorithm

Application Scenario: Optimal Assignment of Tasks to Workers

Problem Setup:

• 3 workers: Alice, Bob, and Charlie

• 3 tasks: T1, T2, T3

• A cost matrix is given, where each element represents the cost (e.g., time or money) for a worker to perform a task.

• The goal is to assign one task to each worker such that the total cost is minimized.

Implementation in Python using SciPy

import numpy as np
from scipy.optimize import linear_sum_assignment

# Cost matrix: rows = workers, columns = tasks
# cost[i][j] = cost of assigning worker i to task j
cost = np.array([
    [9, 2, 7],   # Alice
    [6, 4, 3],   # Bob
    [5, 8, 1]    # Charlie
])

# Solve the assignment problem using the Hungarian Algorithm
row_ind, col_ind = linear_sum_assignment(cost)

# Display results
total_cost = cost[row_ind, col_ind].sum()
print("Assignment result:")
for i, j in zip(row_ind, col_ind):
    print(f"Worker {i} → Task {j} (Cost: {cost[i][j]})")
print(f"Total cost: {total_cost}")

Example Output

Assignment result:
Worker 0 → Task 1 (Cost: 2)
Worker 1 → Task 2 (Cost: 3)
Worker 2 → Task 0 (Cost: 5)
Total cost: 10

→ Optimal assignment:

• Alice → T2,

• Bob → T3,

• Charlie → T1,
  → Total cost = 10

Other Real-World Use Cases

Adapting for Maximization Problems

If your problem involves gains or profits instead of costs, you can convert it into a minimization problem using the following approach:

profit = np.array([
    [10, 3, 5],
    [2, 8, 7],
    [6, 4, 9]
])

# Convert profit to cost: cost = max_value - profit
cost = profit.max() - profit

row_ind, col_ind = linear_sum_assignment(cost)

This allows linear_sum_assignment() to maximize total gain by minimizing the transformed cost.

Additional Notes

• scipy.optimize.linear_sum_assignment() provides an efficient implementation of the Kuhn–Munkres algorithm.

• Even for larger matrices, it operates in O(n³) time, making it suitable for real-world scale assignment problems.

Application Examples of the Kuhn–Munkres Algorithm

The Kuhn–Munkres algorithm (Hungarian Method) is widely applied to real-world one-to-one assignment problems. Below are detailed use cases across various domains:

1. Manufacturing & Industry: Assignment of Robots/Machines to Tasks

Overview:

• • Tasks vary in required skills, locations, and duration.

  • A cost matrix is defined based on each robot’s capabilities and travel distance.

Examples:

• • Optimal assignment of robots to assembly tasks in car manufacturing plants.

  • Matching wafer-processing machines with jobs in semiconductor fabs.

Objective: Minimize total operation time or energy consumption.

2. Education & Academia: Student–Lab/Professor Assignment

Overview:

• • A preference or satisfaction matrix is created based on students’ choices and lab requirements.

  • Treated as a maximum gain assignment problem.

Examples:

• • Lab assignment systems at universities.

  • Automated recommendation/admission matching in Japanese university entrance systems.

Objective: Maximize satisfaction and ensure fair placements.

3. Healthcare: Matching Doctors/Nurses with Patients

Overview:

• • Cost is derived from doctor specialization, patient urgency, and waiting time.

  • Enables priority assignment for critical cases.

Examples:

• • Hospital selection during emergency transport (considering distance and treatment feasibility).

  • Scheduling doctors with patient appointments.

Objective: Balance medical workload and maximize treatment efficiency.

4. Computer Vision: Object Tracking Across Frames

Overview:

• • Estimate object correspondences between frames using a similarity or distance matrix.

Examples:

• • Multi-object tracking (MOT) systems linking detections to existing tracks.

  • Vehicle or pedestrian tracking in surveillance systems.

Objective: Minimize ID switches and tracking errors.

5. Natural Language Processing (NLP): Element Alignment / Translation Matching

Overview:

• • Match words or phrases across two sentences based on semantic or grammatical similarity.

  • The similarity matrix is treated as a gain matrix.

Examples:

• • Alignment in machine translation systems.

  • Mapping subject–verb–object relationships in a sentence.

Objective: Improve translation accuracy and semantic analysis.

6. Logistics & Warehousing: Package–Vehicle Assignment

Overview:

• • Costs are defined based on weight, distance, urgency, and vehicle capacity/location.

Examples:

• • Optimizing last-mile delivery assignment.

  • Allocating autonomous mobile robots (AGVs) to transport tasks in a warehouse.

Objective: Maximize delivery efficiency, minimize total cost.

7. Event & Exam Operations: Room–Session/Test Assignment

Overview:

• • Optimize room usage based on capacity, equipment, and location constraints.

Examples:

• • TOEIC or university exam room allocation.

  • Conference scheduling and session–room mapping.

Objective: Optimize seating arrangement and equipment utilization.

Extended Applications in AI & Automation

AI Scheduler Integration

• • Agents automatically assign tasks or shifts to workers.

  • Useful in workforce planning, delivery optimization, and personnel deployment.

Recommender Systems: User–Item Matching

• • Gain matrix based on affinity scores between users and items.

  • Efficient product assignment within limited slots (inventory or ad space).

Multi-Agent Coordination & Planning

• • Multiple AI agents coordinate shared resources, goals, and tasks.

  • Applied in swarm robotics, distributed task planning, and intelligent transport systems.

References

1. Foundational Papers

Harold W. Kuhn (1955)
Title: The Hungarian Method for the Assignment Problem
Journal: Naval Research Logistics Quarterly
Summary: Introduced the first polynomial-time algorithm for the assignment problem. Explores the connection between linear programming and bipartite graph matching.

James Munkres (1957)
Title: Algorithms for the Assignment and Transportation Problems
Journal: Journal of the Society for Industrial and Applied Mathematics
Summary: Improved Kuhn’s method and established the modern version of the Kuhn–Munkres algorithm.

2. Textbooks & Learning Resources

Introduction to Algorithms (CLRS)
Authors: Cormen, Leiserson, Rivest, Stein
Content: Chapter 29 “Matching and Flow” explains the theoretical background and mechanics of the Hungarian Method.

Combinatorial Optimization: Algorithms and Complexity
Authors: Christos Papadimitriou, Kenneth Steiglitz
Content: Detailed coverage of linear programming and assignment problem theory, including applications of the Hungarian Method.

Algorithm Illustration Book (Japanese: アルゴリズム図鑑)
Author: Yasuteru Ishida
Content: Visually intuitive explanation of the Hungarian Method, well-suited for beginners.

3. Implementations & Tutorials

SciPy
Function: scipy.optimize.linear_sum_assignment
Description: Efficient Python implementation of the Kuhn–Munkres algorithm.

CP-Algorithms
Content: C++ implementation with detailed theoretical explanations. Popular among competitive programmers.

GitHub – HungarianAlgorithm
Content: Multi-language implementations (Python, C++, Java) under MIT license.

4. Applications & Research Studies

D. P. Bertsekas (1988)
Title: The Auction Algorithm: A Distributed Relaxation Method for the Assignment Problem
Summary: A distributed alternative to the Kuhn–Munkres method for solving assignment problems.

Combinatorial Optimization
Authors: Cook, Cunningham, Pulleyblank, Schrijver
Summary: Comprehensive coverage of assignment problems, matching, linear programming, and real-world optimization cases in industry.

Domain-Specific Applications

• Computer Vision:
  Multi-Object Tracking using the Hungarian Algorithm
  (e.g., CVPR conference papers)

• Natural Language Processing (NLP):
  Word alignment in Statistical Machine Translation (SMT)

• Education Economics:
  Matching students to schools (e.g., Gale–Shapley variants and optimal assignment mechanisms)