Hungarian Assignment Algorithm

A newsletter for Applied Math and Computer Science. Subscribe.

This is part of our Applied Optimal Transport for Programmers Series:

1. Chapter 1: Sinkhorn-Knopp Algorithm for Solving Optimal Transport Problems.
2. Chapter 2: Sinkhorn Solves Sudoku - Optimal Transport for Machine Learning.
3. Chapter 3: Gumbel-Sinkhorn Networks and Neural Sorting Algorithms.
4. Chapter 4 (we are here): Hungarian Assignment with Sinkhorn reductions.

1.0 Paper Introduction

The Hungarian Method for The Assignment Problem (Kuhn, 1955)1 introduces a polynomial-time minimization algorithm for allocating tasks to resources on a strict one-to-one basis.

Here are practical problems the Hungarian algorithm solves:

1. 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 (Wikipedia, 2025)2.
2. 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)3
3. 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 Hungarian algorithm relies on the Sinkhorn-Knopp matrix-balancing algorithm that we covered it in detail earlier.

The original 1955 algorithm has O(n4) complexity. Modern systems like Scipy’s optimize use the Jonker-Volgenant linear sum assignment with O(n3) complexity (Scipy, 2025)4.

1.1 Problem Setup

Say we have a warehouse with five delivery riders. There are five routes and each rider charges different amounts for each route.

There are 5! = 120 possible assignments. For instance, a random assigment that resembles the table below costs 468 dollars:

It takes factorial time to find all possible assignments. This is impossible to solve for matrices with 120 rows or more.

Hungarian’s algorithm states that we can do this in polynomial time to find the lowest possible cost assignment. In this case its 368 dollars and these are the best delivery assignment routes:

2.0 Kuhn’s Algorithm

Code is available on GitHub.

Kuhn’s algorithm involves 6 steps that resemble the Sinkhorn-Knopp matrix-balancing algorithm (GeeksForGeeks, 2025)5:

Here’s the corresponding Python code:

from collections import deque
import sys

def InitalizeLabels(costMatrix,leftLabels):
    for row in range(len(costMatrix)): leftLabels[row]=max(costMatrix[row])

def AddTreeNode(x,parentX,treeX,parent,slack,slackX,leftLabels,rightLabels,costMatrix):
    treeX[x],parent[x]=True,parentX
    for y in range(len(slack)):
        value=leftLabels[x]+rightLabels[y]-costMatrix[x][y]
        if value Route {route+1}: {costMatrix[rider][route]}")

    print(f"Total Cost: {totalCost}")

Running this code yields the following assignment in polynomial time:

Rider 1 -> Route 3: 80
Rider 2 -> Route 5: 80
Rider 3 -> Route 4: 57
Rider 4 -> Route 2: 55
Rider 5 -> Route 1: 88
Total Cost: 360

It worked in polynomial time and it was fast. Zero need for factorial search!

2.1 Bonus Content: Faster Than Hungarian Algorithm

The Hungarian algorithm is far from state of the art and the Jonker-Volgenant algorithm is preferred for linear assigment (StackOverflow, 2023)6.

For the curious, one can use Scipy’s linear_sum_assignment function to achieve the same:

from scipy.optimize import linear_sum_assignment
def MinimizeCost_LinearSum(costMatrix):
    riderIndexes,routeIndexes=linear_sum_assignment(costMatrix)
    totalCost=sum(costMatrix[rider][route] for rider,route in zip(riderIndexes,routeIndexes))
    return totalCost,riderIndexes,routeIndexes
if __name__=="__main__":
    costMatrix=[[100,101,80,55,90],[90,102,75,60,80],[85,75,101,57,95],[93,55,102,88,125],[88,125,90,95,105]]
    totalCost2,riderIndexes,routeIndexes=MinimizeCost_LinearSum(costMatrix)

For the extremely curious, Scipy’s Jonker-Volgenant is 40 times faster than the original algorithm. Here’s benchmarking code:

import random
import time
import statistics

def BenchmarkAlgorithms(matrixSizes,numberOfRuns=5):
    print(f"{'Size':<10}{'Hungarian (s)':<20}{'Linear Sum (s)':<20}{'Speedup':<10}")
    print("-"*60)

    for size in matrixSizes:
        hungarianTimes=[]
        linearSumTimes=[]

        for _ in range(numberOfRuns):
            costMatrix=[[random.randint(1,1000) for _ in range(size)] for _ in range(size)]

            startTime=time.perf_counter()
            MinimizeCost_Hungarian(costMatrix)
            hungarianTimes.append(time.perf_counter()-startTime)

            startTime=time.perf_counter()
            MinimizeCost_LinearSum(costMatrix)
            linearSumTimes.append(time.perf_counter()-startTime)

        averageHungarian=statistics.mean(hungarianTimes)
        averageLinearSum=statistics.mean(linearSumTimes)
        speedup=averageHungarian/averageLinearSum

        print(f"{size:<10}{averageHungarian:<20.6f}{averageLinearSum:<20.6f}{speedup:.2f}x")
if __name__=="__main__":
    BenchmarkAlgorithms([5,10,20,30,40,50,75,100],5)

These are the results:

Size      Hungarian (s)       Linear Sum (s)      Speedup   
------------------------------------------------------------
5         0.000219            0.000047            4.66x
10        0.000482            0.000063            7.66x
20        0.001088            0.000087            12.48x
30        0.003787            0.000191            19.86x
40        0.005188            0.000195            26.61x
50        0.006721            0.000261            25.79x
75        0.016902            0.000577            29.30x
100       0.039297            0.000997            39.41x

3.0 Recommended Reading

If this interests you then check out our Applied Optimal Transport for Programmers Series:

1. Chapter 1: Sinkhorn-Knopp Algorithm for Solving Optimal Transport Problems.
2. Chapter 2: Sinkhorn Solves Sudoku - Optimal Transport for Machine Learning.
3. Chapter 3: Gumbel-Sinkhorn Networks and Neural Sorting Algorithms.

Subscribe now

References

1

Kuhn, H.W. (2010). The Hungarian Method for the Assignment Problem. In: Jünger, M., et al. 50 Years of Integer Programming 1958-2008. Springer, Berlin, Heidelberg. DOI.

2

Wikipedia Authors. (2025). Hungarian Algorithm. Link.

3

SLM MBA Authors. (2025). Step-by-Step Guide to Solving Assignment Problems Using the Hungarian Method. Link.

4

Scipy Authors. Linear Sum Assignment. Link.

5

Geeks for Geeks Authors. (2025). Hungarian Algorithm for Assignment Problem (Introduction and Implementation). Link.

6

StackOverflow, User:Alonso. (2023). Faster alternatives to the Hungarian Algorithm?. StackOverflow Website. Link.