Coding the 1955 paper that introduced the Hungarian Algorithm, a polynomial-time minimization algorithm for allocating tasks to resources on a strict one-to-one basis.
For the curiousm, here are practical problems the Hungarian algorithm solves:
- You have three workers, one to clean, another to sweep and another to wash. They each demand different pay for the tasks. The goal is to find the lowest-cost way to assign the jobs.
- You operate an e-commerce warehouse with five delivery riders and five routes. Each takes different time based on traffic, familiarity and vehicle type. How do you assign routes to the riders for the lowest possible delivery time? (SLM MBA, 2025)
- You trained a Gumbel-Sinkhorn sorting network. Now you need to assign the resulting doubly-stochastic matrices to permutation matrices using the Hungarian algorithm.
The repo is written to be followed alongside this LeetArxiv article.
Clone the repo and run using:
jupyter notebook
This is part of our Applied Optimal Transport for Programmers Series:
- Chapter 1: Sinkhorn-Knopp Algorithm for Solving Optimal Transport Problems.
- Chapter 2: Sinkhorn Solves Sudoku - Optimal Transport for Machine Learning.
- Chapter 3: Gumbel-Sinkhorn Networks and Neural Sorting Algorithms.
- Chapter 4 (we are here): Hungarian Assignment with Sinkhorn reductions.