
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 lowestcost 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: Pseudocode for Murty's Algorithm.
queue that has the best solution. The solution to this problem P is the secondbest 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 thirdbest solution to P0. And so on.
Since we perform one partitioning for each of the kbest 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 worstcase 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.