page 3  (17 pages) 2 4

1. Find the best solution, S0, to P0.

2. Initialize a priority queue of problem/solution pairs to contain only < P0; S0 >. The top pair on this queue will always be the pair with
the lowest-cost solution.

3. Clear the list of solutions to be returned.

4. For i = 1 to k, or until the priority queue of problem/solution pairs is empty:
f

4.1. Take the top problem/solution pair, hP; Si, off the queue.
4.2. Add S to the list of solutions to be returned.
4.3. For each triple, < y; z; l >, found in S:
f
4.3.1. Let P = P.
4.3.2. Remove the triple < y; z; l > from P .
4.3.3. Find the best solution, S0, to P .
4.3.4. If S0 exists:
f
4.3.4.1. Add < P ; S0 > onto the queue of problem/solution pairs.
g
4.3.5. From P, remove triples that include y, and all triples that
include z, except for < y; z; l > itself.
g
g

g

Figure 1: Pseudo-code for Murty's Algorithm.

queue that has the best solution. The solution to this problem P is the second-best solution to P0. Now we remove P from the queue and replace it by its partitioning. The best solution found in the queue now is the third-best solution to P0. And so on.

Since we perform one partitioning for each of the k-best solutions, we find, in the worst case, each partitioning creates O(N) new problems. This creates up to O(kN) assignment problems and insertions on the priority queue. Each problem takes at most O(N3) time to solve, and each insertion takes at most O(kN) time,1 so, without any optimizations, the worst-case execution time of Murty's method is O(kN(N3 +kN )), or O(kN4) if k <= N2.
1Note, however, that our implementation has O(N2) worst case for enqueuing.