[SciPy-Dev] ENH: Add an approximate Linear Sum Assignment Solver

[Ali Saad-Eldin]

Hi all,
Hi all,

I would like to add an approximate Linear Assignment Problem<http://www.assignmentproblems.com/doc/LSAPIntroduction.pdf> (aLAP) solver to scipy.optimize. The specific approximation algorithm I propose adding can be found here<https://link.springer.com/content/pdf/10.1007%2F978-3-540-68111-3_74.pdf>. Scipy.optimize currently houses an exact solver for LAP in linear_sum_assignment()<https://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.linear_sum_assignment.html>, and I was thinking this could be added either as a new method within linear_sum_assignment(), or as its own function.

The approximation algorithm has time complexity O(n2log(n)), compared to the algorithm implemented in linear_sum_assignment() with complexity ~O(n2.3 ), while guaranteeing a score >= 1/2 optimum (though in practice the scores appear to be much closer to optimum).   I've attached two plots demonstrating runtime and accuracy, running linear_sum_assignment() and aLAP on simulated, dense nxn cost_matrices with entries randomly selected from a uniform(0,100) distribution, for n sampled from [0, 3000]. Note that linear_sum_assignment() is essentially C/C++, while the aLAP implementation is native Python, so a cython implementation could make aLAP even faster. Additionally, an advantage to this algorithm is that it is parallelizable, which could cause a further speed up.

Current version of the implementation can be found here<https://github.com/neurodata/graspy/blob/ase-alap/graspy/match/alap.py>, and proof of effectiveness here<https://nbviewer.jupyter.org/github/asaadeldin11/nbview/blob/master/aLAP_code.ipynb>.

Best,
Ali Saad-Eldin
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/scipy-dev/attachments/20200710/a6dffa16/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: perdiff_lapvalap.png
Type: image/png
Size: 43428 bytes
Desc: perdiff_lapvalap.png
URL: <http://mail.python.org/pipermail/scipy-dev/attachments/20200710/a6dffa16/attachment-0002.png>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: time_lapvalap.png
Type: image/png
Size: 51863 bytes
Desc: time_lapvalap.png
URL: <http://mail.python.org/pipermail/scipy-dev/attachments/20200710/a6dffa16/attachment-0003.png>