View License

Download apps, toolboxes, and other File Exchange content using Add-On Explorer in MATLAB.

» Watch video

Highlights from
Functions for the rectangular assignment problem

4.5 | 29 ratings Rate this file 42 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.

| Watch this File

File Information

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);


This file inspired A Framework For Structural Input/Output And Control Configuration Selection In Large Scale Systems, Rectangular Maximal Assignment With Lattice Of Dual Price, Munkres Assignment Algorithm, 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 (36)
20 Feb 2017 Alex Nikitin

23 Jun 2016 Uubu

Uubu (view profile)

30 Mar 2016 Shan Muga

23 May 2015 Xin Liu

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 ?

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

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

Yu (view profile)

09 Nov 2011 yair

yair (view profile)

Hello Markus.

Is it a O(n^3) implementaion?

Comment only
20 Oct 2011 James

James (view profile)

Great work

25 May 2011 Andy

Andy (view profile)

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?

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

Bruno Luong (view profile)

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


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

Only links added in help lines.

14 Mar 2014 1.4

* Bugfix: free replaced by mxFree in assignmentsuboptimal2.c
* Wrapper for function munkres of Yi Cao ( included for algorithm comparison.

17 Mar 2014 1.5

Updated munkres_wrap.m to be compatible to the version from as well

Contact us