matrixhungarian-algorithm

Second best solution to an assignmentproblem using the Hungarian Algorithm


For finding the best solution in the assignment problem it's easy to use the Hungarian Algorithm. For example:

A |  3  4  2
B |  8  9  1
C |  7  9  5

When using the Hungarian Algorithm on this you become:

A |  0  0  1
B |  5  5  0
C |  0  1  0

Which means A gets assigned to 'job' 2, B to job 3 and C to job 1. However, I want to find the second best solution, meaning I want the best solution with a cost strictly greater that the cost of the optimal solution. According to me I just need to find the assignment with the minimal sum in the last matrix without it being the same as the optimal. I could do this by just searching in a tree (with pruning) but I'm worried about the complexity (being O(n!)). Is there any efficient method for this I don't know about?

I was thinking about a search in which I sort the rows first and then greedily choose the lowest cost first assuming most of the lowest costs will make up for the minimal sum + pruning. But assuming the Hungarian Algorithm can produce a matrix with a lot of zero's, the complexity is terrible again...


Solution

  • What you describe is a special case of the K best assignments problem -- there was in fact a solution to this problem proposed by Katta G. Murty in the following 1968 paper "An Algorithm for Ranking all the Assignments in Order of Increasing Cost." Operations Research 16(3):682-687.

    Looks like there are actually a reasonable number of implementations of this, at least in Java and Matlab, available on the web (see e.g. here.)