image thumbnail

Fast Linear Assignment Problem using Auction Algorithm (mex)

version 2.6.0.0 (5.7 KB) by Florian Bernard
Mex Implementation of Bertsekas' auction algorithm for solving the linear assignment problem

1.3K Downloads

Updated 01 Feb 2017

View License

Mex implementation of Bertsekas' auction algorithm [1] for a very fast solution of the linear assignment problem.
The implementation is optimised for sparse matrices where an element A(i,j) = 0 indicates that the pair (i,j) is not possible as assignment. Solving a sparse problem of size 950,000 by 950,000 with around 40,000,000 non-zero elements takes less than 8 mins. The method is also efficient for dense matrices, e.g. it can solve a 20,000 by 20,000 problem in less than 3.5 mins.
Both, the auction algorithm and the Kuhn-Munkres algorithm have worst-case time complexity of (roughly) O(N^3). However, the average-case time complexity of the auction algorithm is much better. Thus, in practice, with respect to running time, the auction algorithm outperforms the Kuhn-Munkres (or Hungarian) algorithm significantly.
When using this implementation in your work, in addition to [1], please cite our paper [2].

[1] Bertsekas, D.P. 1998. Network Optimization: Continuous and Discrete Models. Athena Scientific.
[2] Bernard, F., Vlassis, N., Gemmar, P., Husch, A., Thunberg, J., Goncalves, J. and Hertel, F. 2016. Fast correspondences for statistical shape models of brain structures. SPIE Medical Imaging, San Diego, CA, 2016.

The author would like to thank Guangning Tan for helpful feedback. If you want to use the Auction algorithm without Matlab, please check out Guangning Tan's C++ interface, available here: https://github.com/tgn3000/fastAuction .

Cite As

Florian Bernard (2021). Fast Linear Assignment Problem using Auction Algorithm (mex) (https://www.mathworks.com/matlabcentral/fileexchange/48448-fast-linear-assignment-problem-using-auction-algorithm-mex), MATLAB Central File Exchange. Retrieved .

MATLAB Release Compatibility
Created with R2016a
Compatible with any release
Platform Compatibility
Windows macOS Linux

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!