How to Learn Murty’s Algorithm: Ranked Assignments, Partitioned Subproblems, Priority Queues and K-Best Data Association

What if the cheapest assignment is not enough? In tracking, scheduling, diagnosis and decision systems, the best solution may be only one plausible hypothesis. Murty’s algorithm turns a single-best assignment solver into a ranked generator: best, second-best, third-best, and onward, without enumerating every permutation.

This article teaches Murty’s algorithm as a Learning Hall progression from a 3×3 cost matrix to professional k-best data-association engineering. It complements the Hungarian Algorithm article, whose canonical job is finding one optimal assignment, and the broader Bipartite Matching article. Murty’s distinct job is to rank multiple complete assignments by repeatedly solving carefully constrained subproblems.

Quick Read

An assignment chooses one compatible column for each row, with no column reused.
A standard assignment solver returns one minimum-cost assignment.
Murty’s method partitions the remaining assignment space into disjoint constrained subproblems.
Each subproblem has its own best feasible assignment and cost.
A min-priority queue stores those candidate subproblems.
Pop the cheapest candidate: that is the next ranked assignment.
Partition that candidate’s subproblem again, push its feasible children, and repeat until k assignments have been produced.
Professional implementations reuse information from parent solves, handle ties and infeasibility explicitly, and stop early when only a small k is needed.

1. Beginner Level: One Assignment Is One Permutation

Suppose three workers must take three different jobs. The cost matrix is:

        Job A  Job B  Job C
Worker 1   4      1      3
Worker 2   2      0      5
Worker 3   3      2      2

A complete assignment picks exactly one entry from each row and each column. With three rows there are at most 3! = 6 permutations, so a beginner can list them all and sort by total cost. But at n = 20 there are 20! possible permutations—about 2.43×10¹⁸. Ranking by brute force is no longer a plan.

2. The Key Shift: Rank Subproblems, Not Raw Permutations

Murty’s insight is that we do not need to generate every assignment in order. We need a way to divide the unseen assignments into disjoint groups and ask a trusted assignment solver for the cheapest member of each group.

Each group becomes a constrained assignment subproblem. Some row–column pairs may be fixed; others may be forbidden. The cheapest solution of a subproblem is a lower frontier for everything still hidden inside that subproblem. This allows a best-first search over whole regions of assignment space.

3. Partitioning Around the Current Best Assignment

Suppose the current best assignment, written in row order, is:

r1 → c2
r2 → c1
r3 → c3

To cover every different assignment exactly once, we can partition by the first row at which an alternative differs:

Child 1: forbid r1→c2.
Child 2: fix r1→c2, but forbid r2→c1.
Child 3: fix r1→c2 and r2→c1, but forbid r3→c3.

Every assignment other than the current one has a first row where it differs, so it belongs to one of these children. The children are disjoint because each chooses a different first deviation point. That disjointness is the mathematical reason the ranking can avoid duplicate regions.

4. The Priority Queue Is the Ranking Engine

Solve every feasible child subproblem and put its cheapest assignment into a min-priority queue keyed by total cost. The smallest queue item is the cheapest assignment remaining anywhere among the current partitions, so it becomes the next output.

Then partition the subproblem from which that assignment came, solve its children, push them, and repeat. Murty’s method therefore looks like a best-first search whose nodes are constrained assignment problems rather than ordinary graph vertices.

5. Conceptual Pseudocode

root = unconstrained assignment problem
best = solve_assignment(root)
output best

Q = empty min-priority queue
push every feasible partition child of root/best into Q

while Q is not empty and fewer than k assignments have been output:
    node = pop cheapest subproblem from Q
    output node.best_assignment

    children = partition(node, node.best_assignment)
    for child in children:
        child_solution = solve_assignment(child)
        if child_solution is feasible:
            push child_solution into Q

The assignment solver may be Hungarian, shortest-augmenting-path based, auction-based, or another correct method. Murty’s outer logic does not replace that solver; it repeatedly calls it under different fixed/forbidden constraints.

6. A Tiny Reference Oracle Before Murty

Before implementing ranked subproblems, build a brute-force oracle for tiny matrices. It is not a production algorithm. Its job is to give you a ground truth against which the first few Murty outputs can be tested.

from itertools import permutations

def brute_rank_assignments(cost):
    n = len(cost)
    ranked = []
    for cols in permutations(range(n)):
        total = sum(cost[r][cols[r]] for r in range(n))
        ranked.append((total, cols))
    return sorted(ranked)

cost = [
    [4, 1, 3],
    [2, 0, 5],
    [3, 2, 2],
]

for item in brute_rank_assignments(cost):
    print(item)

For n = 3 or 4, this reference is excellent for debugging. For n = 12, it is already absurdly expensive. That contrast makes the purpose of Murty’s partitioning concrete.

7. A Teaching Skeleton with a Real Assignment Solver

SciPy’s linear_sum_assignment can solve the single-best linear sum assignment problem. A Murty implementation can wrap it by constructing child subproblems whose fixed choices remove rows and columns and whose forbidden choices are masked from the residual matrix.

from scipy.optimize import linear_sum_assignment
import numpy as np

def solve_single(cost):
    rows, cols = linear_sum_assignment(np.asarray(cost, dtype=float))
    total = float(np.asarray(cost)[rows, cols].sum())
    return total, tuple(zip(rows.tolist(), cols.tolist()))

# Murty's outer layer adds:
# 1. fixed row-column pairs
# 2. forbidden row-column pairs
# 3. a min-heap of solved subproblems
# 4. disjoint partitioning after each popped solution

Strong learners should first implement the subproblem representation and feasibility checks separately. Trying to write the entire ranked solver in one pass makes it too easy to confuse assignment constraints with heap logic.

8. The Invariant: The Heap Covers Everything Not Yet Output

After each output, the active subproblems in the priority queue should form a disjoint cover of every feasible assignment not yet emitted. Each queue key is the cost of the best solution inside that region. Therefore the smallest key corresponds to the globally next-best unseen assignment.

This invariant is the heart of correctness. If the partitions overlap, duplicates can appear. If they leave a gap, a valid assignment can disappear from the ranking. If a queue key is not the true optimum for its subproblem, the output order can be wrong.

9. Ties: “Second” Does Not Always Mean Higher Cost

Two distinct assignments can have exactly the same total cost. A ranked-assignment API therefore needs an explicit policy: output all distinct assignments even when costs tie, impose a deterministic tie-break order, or group equal-cost assignments as one rank level.

Floating-point costs complicate equality further. Professional code should not casually compare decimal sums for exact equality when those costs came from numerical estimation. Decide whether ranking is by exact stored cost, a tolerance band, or a secondary deterministic key.

10. Complexity: The Base Solver Still Matters

Murty’s original 1968 paper describes the extra work for producing another ranked assignment in terms of solving at most n−1 additional assignment problems, with problem sizes ranging through smaller subproblems. The practical end-to-end cost therefore depends strongly on the underlying assignment solver, the number k requested, how quickly children become infeasible, and how much information can be reused between related solves.

A poor complexity statement is “Murty is O(k n³)” with no qualifications. That shorthand may approximate some implementations using cubic assignment solves, but it hides partition sizes, reuse, heap operations and optimisations. Professional analysis should name the base solver and the actual subproblem strategy.

11. Why Modern Implementations Are Faster Than the Simplest Version

Miller, Stone and Cox studied optimisations to Murty’s ranked assignment method for data association. The broader engineering lesson is important: child subproblems are close relatives of their parents. Reusing dual information, partial assignment state or lower-bound information can avoid treating every child as an unrelated problem from scratch.

Warm-start related assignment solves when the solver supports it.
Keep lower bounds and discard provably uncompetitive subproblems when the application allows bounded ranking.
Choose partition order deliberately.
Represent fixed and forbidden pairs compactly instead of copying an entire cost matrix for every child.
Use a heap so retrieving the next candidate is logarithmic in the number of active subproblems.

12. Where K-Best Assignments Matter

Multi-target tracking: several nearly equal measurement-to-track associations may need to survive into later probabilistic reasoning.
Sensor fusion: downstream evidence can disambiguate associations that are hard to separate locally.
Scheduling: operators may want the best few feasible schedules, not only one brittle optimum.
Contingency planning: the second- or third-best assignment can become useful when a resource fails.
Decision support: showing alternatives can expose whether the optimum is robust or only marginally better than nearby choices.

The reason to compute k-best solutions should come from the receiver. If the downstream system will use only one assignment, producing 10,000 alternatives is wasted work.

13. Failure Modes Strong Learners Should Test

Overlapping partitions: the same assignment can appear through two subproblems.
Incomplete partitions: a valid assignment may never be generated.
Ignoring infeasibility: fixed and forbidden constraints can leave no complete assignment.
Duplicate outputs: ties or inconsistent partition bookkeeping can emit the same row-column mapping twice.
Rectangular confusion: the meaning of a complete assignment changes when row and column counts differ.
Infinity and NaN misuse: simply dropping huge sentinels into a cost matrix can interact badly with numerical solvers.
Heap ordering only by cost: equal costs may need a stable secondary key to keep behaviour deterministic.
Requesting impossible k: there may be fewer than k feasible assignments.
Factorial reference code leaking into production: brute force belongs only in tiny tests.
Assuming k-best means k distinct cost values: distinct assignments can share one cost.

14. Professional-Level Engineering

At production scale, measure three quantities separately: time spent in assignment solves, time spent managing the ranked-subproblem heap, and memory consumed by active partitions. Different datasets stress different parts of the algorithm. A sparse feasible-assignment graph may create infeasible children quickly; a dense near-tied cost matrix may keep many plausible alternatives alive.

For tracking systems, ranking speed is only one requirement. The assignment costs themselves must correspond to a defensible statistical or geometric model, and downstream consumers must know whether costs are comparable across frames or hypotheses. Murty can rank whatever numbers you give it; it cannot make badly calibrated costs meaningful.

15. How to Learn It Without Memorising It

The hardest idea for learners is usually not the priority queue. It is understanding that a partition describes a set of assignments. Use worked examples where the learner predicts which permutations belong to each child before any code is shown.

Predict: enumerate all six assignments of a 3×3 problem and identify the first deviation from the optimum.
Run: draw the partition tree and write the best cost inside every active subproblem.
Investigate: verify that the children are disjoint and cover all unseen assignments.
Modify: add a forbidden edge and predict which branches become infeasible.
Make: replace the brute-force oracle with a real assignment solver.
Validate: compare the first k outputs against exhaustive ranking for hundreds of random small matrices.

16. Learning Progression: Beginner to Professional

Beginner: understand complete assignments and rank all 3×3 permutations by hand.
Intermediate: partition by first deviation and use a heap to generate ranked candidates.
Advanced: implement fixed/forbidden constraints, rectangular cases, tie policy and infeasibility handling.
Professional: reuse solver state, benchmark k-sensitive scaling, integrate domain-calibrated costs, and test deterministic behaviour under ties and numerical edge cases.

17. Practice Problems

Rank every assignment of the 3×3 example and verify the first four Murty outputs.
Write the three first-deviation partitions for a four-row optimum.
Construct a matrix with four equal-cost optimal assignments. Define and test a deterministic tie policy.
Forbid one edge used by the optimum and predict which assignment becomes first.
Build a rectangular example with more columns than rows and define what one feasible complete assignment means.
Compare exhaustive ranking with your implementation for random 5×5 integer matrices.
Instrument the code to count base assignment solves per emitted solution as k grows.

18. Sources and Further Reading

Final idea: Murty’s algorithm teaches a reusable professional pattern: when the solution space is enormous but you need only the best few answers, partition the unseen space into disjoint regions, compute a trustworthy bound or optimum for each region, and explore those regions in best-first order.

Small Group Tutorials