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: 
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.](http://pubsonline.informs.org/doi/abs/10.1287/opre.16.3.682)" 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](https://code.google.com/p/java-k-best/).)
In [r](/questions/tagged/r "show questions tagged 'r'") there is now an implementation of Murty's algorithm in the `muRty` package. 

[CRAN](https://cran.r-project.org/web/packages/muRty/index.html) 

[GitHub](https://github.com/arg0naut91/muRty)

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.