Code covered by the BSD License

### Highlights fromFunctions for the rectangular assignment problem

4.78261

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

# Functions for the rectangular assignment problem

14 Dec 2004 (Updated 04 Jul 2011)

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)
Tags for This File
Everyone's Tags
Tags I've Applied
16 May 2013
10 Aug 2012

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

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

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

29 May 2012
09 Nov 2011

Hello Markus.

Is it a O(n^3) implementaion?

20 Oct 2011

Great work

25 May 2011
24 Apr 2011
24 Apr 2011

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

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

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

17 Mar 2009

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

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
28 Oct 2008

Great, thanks for sharing this code!!

09 Oct 2008

Perfect! Keep the good work Up!

11 Jul 2008

You saved me a lot of trouble, thank you!

29 May 2008

Excellent!

23 May 2008
23 May 2008

Many thanks for the code, it works great!

25 Apr 2008

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

23 Apr 2008
22 Apr 2008

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

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

Very nice work. I do appreciate.

30 Jan 2008
12 Jul 2007

very good one!!!!!!!

10 Nov 2005

very fast

28 Oct 2005

works great, easy to use

27 Mar 2005

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.

30 Jan 2008

Documentation updated.

01 Dec 2009

Minor changes.

11 Apr 2011

Only E-mail changed in html documentation.

04 Jul 2011