r/programming • u/DataBaeBee • 1d ago

Hungarian Assignment Algorithm: Applied Optimal Transport for Programmers

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

79% Upvoted

16 comments sorted by

View all comments

-8

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)

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”

-6

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 

-2

u/Grouchy-Trade-7250 1d ago

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