Code covered by the BSD License  

Highlights from
Functions for the rectangular assignment problem

4.78261

4.8 | 25 ratings Rate this file 60 Downloads (last 30 days) File Size: 18.7 KB File ID: #6543

Functions for the rectangular assignment problem

by

 

14 Dec 2004 (Updated )

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

| Watch this File

File Information
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 file inspired A Framework For Structural Input/Output And Control Configuration Selection In Large Scale Systems, Munkres Assignment Algorithm, Rectangular Maximal Assignment With Lattice Of Dual Price, and Munkres For Simulink.

MATLAB release MATLAB 6.5.1 (R13SP1)
Tags for This File   Please login to tag files.
Please login to add a comment or rating.
Comments and Ratings (31)
16 May 2013 Charles Nelatury  
10 Aug 2012 Michal Kvasnicka

Excellent piece of work!

Thanks to guys like Markus MATLAB is the best computing environment in the world!

Markus, could you add to the readme file releveant references (Munkres, Hungarian algorithms, assigment problem in general)?

03 Aug 2012 Umit

Is 'assignmentoptimal(rectMatrix)' is the implementation of Munkres algorithm for rectangular case? It says it is Munkres algorithm but original algorithm is for square matrices. This one should be extended version for rectangular cases, right? Can you confirm this.

29 May 2012 Yu

It is very useful for me, especially can handle rectangle situation. Thanks a lot!

29 May 2012 Yu  
09 Nov 2011 yair

Hello Markus.

Is it a O(n^3) implementaion?

20 Oct 2011 James

Great work

25 May 2011 Andy  
24 Apr 2011 Nazmul Islam  
24 Apr 2011 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?

04 May 2010 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.

03 Apr 2010 Bruno Luong

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

17 Mar 2009 michele pace

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

21 Feb 2009 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!

11 Jan 2009 Clemens Yu  
28 Oct 2008 Harrison Woods

Great, thanks for sharing this code!!

09 Oct 2008 Salha Al-Kuwaiti

Perfect! Keep the good work Up!

11 Jul 2008 Leonid Chindelevitch

You saved me a lot of trouble, thank you!

29 May 2008 Stephen Pan

Excellent!

23 May 2008 Francois Berthiaume  
23 May 2008 Francois Berthiaume

Many thanks for the code, it works great!

25 Apr 2008 Markus Buehren

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

23 Apr 2008 Ldd Lasss  
22 Apr 2008 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.

22 Apr 2008 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.

18 Mar 2008 Hao Cheng

Very nice work. I do appreciate.

30 Jan 2008 A Alpers  
12 Jul 2007 praveen kuppili

very good one!!!!!!!

10 Nov 2005 Coffee Bear

very fast

28 Oct 2005 Tium Tium

works great, easy to use

27 Mar 2005 Raimund Leitner

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

Updates
08 Aug 2005

Bug Fix: Error occured when the distance matrix contained only zeros and infinite values.

18 Sep 2007

Bug in documentation corrected.

29 Oct 2007

Bugfix: Please update if you do not use ONE_INDEXING in assignmentoptimal.c.

14 Nov 2007

Update of contact information in documentation.

01 Dec 2009

Minor changes.

11 Apr 2011

Only E-mail changed in html documentation.

04 Jul 2011

Only links added in help lines.

14 Mar 2014

* Bugfix: free replaced by mxFree in assignmentsuboptimal2.c
* Wrapper for function munkres of Yi Cao (www.mathworks.com/matlabcentral/fileexchange/20328) included for algorithm comparison.

17 Mar 2014

Updated munkres_wrap.m to be compatible to the version from http://www.mathworks.com/matlabcentral/fileexchange/20652 as well

Contact us