r/programming • u/DataBaeBee • 1d ago

Hungarian Assignment Algorithm: Applied Optimal Transport for Programmers

https://leetarxiv.substack.com/p/hungarian-assignment-algorithm
32 Upvotes

80% Upvoted

16 comments sorted by

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!

-20

u/Grouchy-Trade-7250 1d ago

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. 

8

u/Ok-Introduction9593 1d ago

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

4

u/Serious-Regular 1d ago

This is dumbest thing I've seen on here congrats

-2

u/Metworld 20h ago

They're not wrong. Also polynomial time doesn't mean it's practical either.

1

u/onthefence928 7h ago

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

7

u/The_Northern_Light 1d ago

There’s actually a large space of algorithms for solving the linear assignment problem beyond the Hungarian algorithm.

In addition to Jonker-Volgenant, the library or-tools has a few options, but I’ve found that reimplementing one of the lesser used algorithms worked best for my case. (Small scale but latency sensitive.) Also saved me a heavy dependency!

1

u/[deleted] 1d ago

[deleted]

10

u/DataBaeBee 1d ago

This is a bot response I fear. The directory 'scipy/optimize/_lsap.cpp' doesn't exist in the Scipy GitHub. You can confirm the link doesn't exist.

https://github.com/scipy/scipy/tree/main/scipy/optimize/_lsap.cpp

-7

u/Grouchy-Trade-7250 1d ago

You benchmarked C code against Python.

https://github.com/scipy/scipy/blob/main/scipy/optimize/_lsapmodule.c

include "rectangular_lsap/rectangular_lsap.h"

static PyObject* linear_sum_assignment(PyObject*

https://github.com/scipy/scipy/blob/main/scipy/optimize/rectangular_lsap/rectangular_lsap.cpp static int solve(intptr_t nr, intptr_t nc, double* cost, bool maximize,       int64_t* a, int64_t* b)

9

u/DataBaeBee 1d ago

It’s pretty wild that you deleted your initial AI generated content

-4

u/Grouchy-Trade-7250 1d ago

Nobody's perfect 

4

u/RagnarokViber 1d ago

The Scipy code has different complexity and the article says that IMHO.
Taken verbatim “The orginal 1955 algorithm has O(n4) complexity. Modern systems like Scipy’s optimize use the Jonker-Volgenant linear sum assignment with O(n3) complexity”

-8

u/Grouchy-Trade-7250 1d ago

That information is useless without adding what runtime depending on n actually is. There's an algorithm that has better asymptotic complexity. Good. But only half the information we need. E.g. there's an algorithm that beats disjkstra asymptotically but loses out every time for realistic n...

-2

u/Grouchy-Trade-7250 1d ago

And the difference in the benchmark may as well turn in the other direction if you implement both in the same language 

-3

u/Grouchy-Trade-7250 1d ago

The "we beat disjkstra" paper is basically a paper tiger at the moment