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_s...>, 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_cod...>. Best, Ali Saad-Eldin
