Code covered by the BSD License

### Highlights from Functions for the rectangular assignment problem

4.80769
4.8 | 28 ratings Rate this file 39 Downloads (last 30 days) File Size: 18.7 KB File ID: #6543 Version: 1.5

# Functions for the rectangular assignment problem

### Markus Buehren (view profile)

14 Dec 2004 (Updated )

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

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
MATLAB release MATLAB 6.5.1 (R13SP1)
23 Jun 2016 Uubu

### Uubu (view profile)

30 Mar 2016 Shan Muga

### Shan Muga (view profile)

23 May 2015 Xin Liu

### Xin Liu (view profile)

31 Oct 2014 Matteo

### Matteo (view profile)

Hi people,
I a question about the hungarian algorithm. this algorithm is optimal algorithm for the assignment problem, and the time complexity is O(n^3), right?
But , if the input is the multidimensional matrix, it's possible to use the hungarian algorithm? how does it change the algorithm and the time complexity ?
thanks

Comment only
16 May 2013 Charles Nelatury

### Charles Nelatury (view profile)

10 Aug 2012 Michal Kvasnicka

### Michal Kvasnicka (view profile)

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

### Umit (view profile)

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.

Comment only
29 May 2012 Yu

### Yu (view profile)

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

29 May 2012 Yu

09 Nov 2011 yair

### yair (view profile)

Hello Markus.

Is it a O(n^3) implementaion?

Comment only
20 Oct 2011 James

Great work

25 May 2011 Andy

### Andy (view profile)

24 Apr 2011 Nazmul Islam

### Nazmul Islam (view profile)

24 Apr 2011 Nazmul Islam

### Nazmul Islam (view profile)

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?

Comment only
04 May 2010 Olivier Planchon

### Olivier Planchon (view profile)

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

### Bruno Luong (view profile)

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

17 Mar 2009 michele pace

### michele pace (view profile)

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

### Greg Fricke (view profile)

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

### Clemens Yu (view profile)

28 Oct 2008 Harrison Woods

### Harrison Woods (view profile)

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!

Comment only
25 Apr 2008 Markus Buehren

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

Comment only
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!!!!!!!

Comment only
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.

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 1.1

Minor changes.

11 Apr 2011 1.2

Only E-mail changed in html documentation.

04 Jul 2011 1.3