Functions for the rectangular assignment problem

This package provides m- and mex-functions for solving the rectangular assignment problem.

Description

With this package, I provide some MATLAB-functions regarding the rectangular assignment problem. This problem appears for example in tracking applications, where one has M existing tracks and N new measurements. For each possible assignment, a cost or distance is computed. All cost values form a matrix, where the row index corresponds to the tracks and the column index corresponds to the measurements. The provided functions return an optimal or suboptimal assignment - in the sense of minimum overall costs - for the given matrix.

In the process of gating, typically very unlikely assignments are forbidden. The given functions can handle forbidden assignments, which are marked by setting the corresponding assignment cost to infinity.

The optimal solution is computed using Munkres algorithm, also known as Hungarian Algorithm.

The functions are called like
[assignment, cost] = assignmentalgorithm(distMatrix);

• Acknowledgements: This submission has inspired the following:; Munkres Assignment Algorithm, Rectangular maximal assignment with lattice of dual price, Munkres for Simulink
• MATLAB release: MATLAB 6.5.1 (R13SP1)

[Raimund Leitner]

Very very good and easy to use implementation of the Munkres algorithm.

[Tium Tium]

works great, easy to use

[Coffee Bear]

very fast

[praveen kuppili]

very good one!!!!!!!

[A Alpers]

 

[Hao Cheng]

Very nice work. I do appreciate.

[Tom Pinkiewicz]

Thanks Markus. This code works great. I re-packaged your c function and integrated it into Simulink. I've posted it on this website.

[Tom Pinkiewicz]

Thanks Markus. This code works great. I re-packaged your c function and integrated it into Simulink. I've posted it on this website.

[Ldd Lasss]

 

[Markus Buehren]

Ldd Lasss, please let me know why you gave a bad rating for my package!

[Francois Berthiaume]

Many thanks for the code, it works great!

[Francois Berthiaume]

 

[Stephen Pan]

Excellent!

[Leonid Chindelevitch]

You saved me a lot of trouble, thank you!

[Salha Al-Kuwaiti]

Perfect! Keep the good work Up!

[Harrison Woods]

Great, thanks for sharing this code!!

[Clemens Yu]

 

[Greg Fricke]

Thank you Markus!
This has helped me pass a critical practicality hurdle in my Master's Research without spending a week or two reading, writing, and debugging!

[michele pace]

Hi, I used assignmentoptimal.* in a multitracking application, exactly in the scenario you described. It works very well. Great job, thank you.

[Bruno Luong]

Great, does what it claims and fast (I use for multi-target tracking.)

[Olivier Planchon]

Excellent !
I especially like the easy-to-use MEX files, and the outstanding test file.
I could optimize my problem beyond my best hope.

[Nazmul Islam]

Thanks a lot for posting this !! I am looking for a Matlab implementation of a maximum weighted matching algorithm in a general graph (not bipartite). Does anyone know a Mathworks thread/link where it has already been posted?

[Nazmul Islam]

 

[Andy]

 

[James]

Great work

[yair]

Hello Markus.

Is it a O(n^3) implementaion?