Feature: new linear_sum_assignment() algorithm

[pfeatherstone]

Looking at scipy, there is a new algorithm that is up to 10X faster than Hungarian algorithm
https://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.linear_sum_assignment.html
https://uk.mathworks.com/matlabcentral/fileexchange/26836-lapjv-jonker-volgenant-algorithm-for-linear-assignment-problem-v3-0
This would be cool

[davisking]

That's maybe what's already in dlib, I forget. There is the vanilla Hungarian algorithm which is O(n^4) and then there are variants like the one you mentioned which are O(n^3). Dlib uses one of the O(n^3) variants, probably the Jonker–Volgenant but at this point I don't remember :|

[pfeatherstone]

Yep will do.

[aditya9710]

i was recently working on Hungarian algorithm implementations for a project. i initially used sciPy’s implementation for prototyping but needed a C++ version for the service implementation. dlib's implementation appears to be of the Kuhn-Munkres variant, typically characterized by O(n^3) time complexity, dual variables, and equality graphs. the current implementation is also limited to integer costs and square matrices. for my use case, i needed support for floating-point types and rectangular matrices, so I developed my own implementation.

i believe dlib could benefit from an update to include a modified Jonker–Volgenant algorithm, which can achieve better time complexities (around O(n^2) or O(n^2 log n)). i’d be happy to help contribute to this effort if there’s interest in incorporating such enhancements.

[arrufat]

I guess these kinds of improvements are always welcome :)

[davisking]

Yeah that would be super cool 😁

[aditya9710]

awesome, will start digging and be back w questions. 🖖