Hi all,

Hi all,

I would like to add an approximate Linear Assignment Problem (aLAP) solver to scipy.optimize. The specific approximation algorithm I propose adding can be found here. Scipy.optimize currently houses an exact solver for LAP in linear_sum_assignment(), 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(n²log(n)), compared to the algorithm implemented in linear_sum_assignment() with complexity ~O(n^2.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, and proof of effectiveness here.