View License

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

» Watch video

Highlights from
K-Best Assignment Algorithm

3.0 | 4 ratings Rate this file 10 Downloads (last 30 days) File Size: 4.29 KB File ID: #30837 Version: 1.0

K-Best Assignment Algorithm


Eric Trautmann (view profile)


Implementation of Murty's algorithm for a ranked list of best assignment solutions.

| Watch this File

File Information

This implementation is based on the 1968 Murty algorithm for finding a ranked list of the best assignments for an arbitrary cost matrix.

This algorithm uses a user-supplied assignment algorithm, such as the Munkres (Hungarian) algorithm or the JV algorithm to obtain an arbitrary number of best assignment solutions.

Implementations of Munkres and JV algorithms by Yi Cao can be found here:




Munkres Assignment Algorithm and Lapjv Jonker Volgenant Algorithm For Linear Assignment Problem V3.0 inspired this file.

MATLAB release MATLAB 7.11 (R2010b)
Other requirements a standard assignment algorithm such as Munkres or JV
Tags for This File   Please login to tag files.
Please login to add a comment or rating.
Comments and Ratings (5)
26 Jul 2016 Tianli Ma

11 Jan 2016 Fernando Iglesias

It does not work properly. Even if you set k=1 and the optimal assignment function provided is correct, the function k_best_assign does not return the correct optimal assignment.

11 Jan 2013 Matthew

Junk code.

10 May 2012 Nick

Nick (view profile)

In my program I choose the JV algorithm as the opt_fun in your function.I think the "k_best_assign" main function has not any problems.But the subfunction "partition_node" is wrong.In the subfunction "partition_node",you classify the node_in matrix as three parts,"the fixed_assignments","the excluded_assignments","the tmp".Then input these three parts to the subfunction "calc_node_cost" to calculate the cost and the new [row col] matrix as the next cycle input.But If we take a good look at the code of the subfunction "partition_node",we will find some logic problems.In the progress of calculate cost,firstly you use the "fixed_assignments" to make summation of some previous fixed data.Then you use the "inf" to replace these data,and calculate the cost again.At last,you add up the summation of some previous fixed data and cost,and think the result is the cost.But you are wrong,because except some special situations,the cost you calculated is "inf" for in your function the fixed_assignments has changed some entire rows and entire columns into "inf" .So,most of the costs you calculate is "inf".Therefore,your comparing all the cost to find the minimum cost is meaningless.

09 May 2012 Dmitri Kamenetsky

Does this code work correctly? I am running

cost_mat = magic(5);
k = 5;
optfun = @munkres;
assignment_list = k_best_assign(cost_mat,k,opt_fun);

The resulting assignment_list has 5 assignments that are all exactly the same, namely [1 1; 1 2; 1 3; 1 4; 1 5] with a cost of 15.

Comment only

Contact us