Second best solution to an assignmentproblem using the Hungarian Algorithm

Question

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

Answer 1

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

Answer 2

In r there is now an implementation of Murty's algorithm in the muRty package.

CRAN

GitHub

It covers:

• Optimization in both minimum and maximum direction;
• output by rank (similar to dense rank in SQL), and
• the use of either Hungarian algorithm (as implemented in clue) or linear programming (as implemented in lpSolve) for solving the initial assignment(s).

Disclaimer: I'm the author of the package.