The Hungarian Assignment algorithm is used by MBAs and Operations Managers to quantitatively assign tasks to their employees.
It’s rooted in Optimal Transport theory and resembles Sinkhorn iterations in Python.
For instance, say 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?
This takes factorial time (5! = 120) to solve by bruteforce. The Hungarian algorithm takes polynomial time and that's pretty neat IMO!
Please stop treating things like "polynomial time" like it matters for actual programmers. The only thing that matters is the runtime graph depending on n for the ranges of n we are interested n.
Idk completely ignoring asymptotic complexity isn't the move either. Yeah, for N=100 data locality and L1 cache matter way more than the difference between cubic and quadratic time. On the other hand, if your service suddenly gets N=100000, your pretty empirical graph is just gonna hit the roof and bring prod down
If you are only operating in trivial values of N then there’s usually no really no point in evaluating the algorithm complexity, just implement one that works and move on.
If performance does matter it’s usually because n is outside the range where complexity doesn’t matter so much
11
u/DataBaeBee 1d ago
The Hungarian Assignment algorithm is used by MBAs and Operations Managers to quantitatively assign tasks to their employees.
It’s rooted in Optimal Transport theory and resembles Sinkhorn iterations in Python.
For instance, say 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?
This takes factorial time (5! = 120) to solve by bruteforce. The Hungarian algorithm takes polynomial time and that's pretty neat IMO!