Algorithms¶
fastlap ships eleven algorithmically distinct solvers behind one dispatch table (src/utils.rs::solve_with), selected via the algorithm= keyword on solve_lap and friends.
>>> fastlap.get_supported_algorithms()
['lapjv', 'hungarian', 'lapmod', 'lapjvsp', 'subgradient', 'auction', 'dantzig', 'sinkhorn', 'ssp', 'cost_scaling', 'greedy']
Each algorithm has its own deep-dive page: motivation, how it works, pseudocode, time/space complexity, a worked example (with a diagram), common pitfalls, and Python usage. The pages below are ordered easy → advanced — roughly, how much background theory each one assumes — not by runtime importance; "lapjv" stays the recommended default regardless of where it falls in this reading order.
New to duals, reduced costs, or augmenting paths?
Read Key Concepts first. It's a short shared glossary — bipartite matching, dual variables, complementary slackness, augmenting paths, approximation ratios, ε-optimality, and the min-cost-flow framing — that every page below assumes.
Comparison table¶
| Algorithm | Approach | Time complexity | Space complexity | Optimal? | Best for |
|---|---|---|---|---|---|
| Greedy | 1/2-approximation greedy edge selection | O(n² log n) | O(n²) | 1/2-approx | Ultra-fast approximate matching |
| Hungarian | Classical Kuhn–Munkres: row/column reduction + zero-covering | O(n³) | O(n²) | Yes | Classical / academic use |
| LAPJV | Column reduction + reduction transfer, then warm-started shortest-augmenting-path | O(n³) worst case | O(n²) | Yes | General-purpose default |
| Subgradient | Coordinate-wise dual ascent warm start, then shortest-augmenting-path completion | O(n³) | O(n²) | Yes | Dual-based warm-up |
| Sinkhorn | Entropic regularized optimal transport (Sinkhorn–Knopp) dual scaling | O(n²) per iter, O(n³) worst-case total | O(n²) | Yes (exact discrete recovery) | Differentiable / OT-adjacent matching |
| Auction | Bertsekas' auction algorithm — bidding/price-raising with ε-scaling | O(n²·k) | O(n²) | ε-optimal | Large square cost matrices |
| SSP | Successive Shortest Path / Min-Cost Max-Flow with exact Johnson potentials | O(n³ log n) | O(n²) | Yes | Graph theory / min-cost flow workflows |
| Cost Scaling | Goldberg–Kennedy push-relabel with cost scaling (ε-relaxation) | O(n³ log(nC)) | O(n²) | Yes | Network flow & cost-scaling research |
| Dantzig | Primal network simplex on the assignment LP, Dantzig's most-negative-reduced-cost pivoting rule | O(n³) typical, O(n⁴) worst-case bound | O(n²) | Yes | Simplex-based / LP-adjacent workflows |
| LAPMOD | Shortest-augmenting-path directly on sparse adjacency — skips densification for scipy.sparse CSR input |
O(rows·nnz) sparse, O(n³) dense | O(n + nnz) sparse, O(n²) dense | Yes | Sparse cost matrices (candidate-gated tracking, large mostly-empty graphs) |
| LAPJVsp | Sparse JV: sparse column reduction + reduction transfer, warm-started sparse SAP — never densifies CSR input | O(nnz) + O(E·log E) per unclaimed row | O(n + nnz) sparse | Yes | True-sparse JV on CSR input (SciPy's min_weight_full_bipartite_matching territory) |
Not sure which to pick?
Start with "lapjv". It's the default, it's exact, and its warm-start preprocessing makes it the fastest exact solver in the suite on most real cost matrices. Reach for a different algorithm only when you have a specific reason — sparse input (LAPMOD or LAPJVsp), an approximate answer under a tight time budget (Greedy), or you're studying a particular algorithm family (Dantzig, SSP, Cost Scaling, Sinkhorn).
Which of these are production-ready?¶
All eleven solvers are correctness-tested against SciPy and an independent exhaustive brute-force oracle, but they are not equally battle-tested. Be honest with yourself about which tier you need:
- Production defaults —
lapjv(dense),lapjvspandlapmod(scipy.sparseinput). These are the ones to reach for. - Exact, but much slower — pick only for the formulation —
hungarian,subgradient,sinkhorn,ssp,cost_scaling,dantzig. - Approximate, not exact-optimal —
auction(ε-optimal),greedy(1/2-approximation).
Measured performance¶
Representative wall-clock timings (best of 3, single core unless noted) on an
Intel Core i9-8950HK (12 threads), NumPy 2.x, release build, versus
scipy.optimize.linear_sum_assignment and lap.lapjv:
| Problem | lapjv | lapjvsp | lapmod | subgradient | auction | sinkhorn | scipy | lap.lapjv |
|---|---|---|---|---|---|---|---|---|
| dense 100×100 | 0.33 ms | 0.71 | 1.17 | 0.89 | 1.18 | 3.72 | 0.29 | 0.17 |
| dense 300×300 | 4.5 ms | 9.2 | 12.0 | 7.4 | 9.3 | 34.1 | 6.3 | 4.6 |
| rect 100×200 | 8.1 ms | 9.8 | 8.1 | — | 8.1 | — | — | — |
| sparse n=2000 d=0.01 | — | 23.5 ms | 46.0 | — | — | — | 16.9 (csgraph) | — |
hungarian (≈377 ms at 300×300), dantzig (≈589 ms), ssp (≈99 ms) and
cost_scaling are exact but far slower on dense problems — they exist for
workflows that specifically want that formulation, not for throughput.
Reproduce this yourself:
Absolute numbers are machine-dependent — track your own with --json.
The eleven algorithms¶
-
A 1/2-approximation baseline: sort every edge, claim the cheapest still-available pair. No duality, no graph search — the simplest thing that could work.
-
Kuhn, 1955 / Munkres, 1957. The textbook zero-covering algorithm — star/prime marks and augmenting paths.
-
Jonker & Volgenant, 1987. Column reduction resolves most rows for free before a warm-started shortest-augmenting-path finishes the rest.
-
Held & Karp, 1971. Coordinate-wise dual ascent builds a warm start for the same shortest-augmenting-path solver LAPJV uses.
-
Cuturi, 2013 (entropic OT); Sinkhorn & Knopp, 1967 (scaling). Matrix-scaling duals, then exact discrete recovery.
-
Bertsekas, 1988. A different paradigm entirely — bidders raise item prices in an economic auction, with ε-scaling for exactness.
-
Successive Shortest Path — min-cost max-flow with Dijkstra and Johnson potentials.
-
Goldberg & Kennedy, 1995. Push-relabel with ε-relaxation, scaled down across phases.
-
Dantzig, 1963. Primal network simplex — an explicit spanning-tree basis with stepping-stone pivots.
-
A sparse-adjacency extension of the shortest-augmenting-path idea — one of two true sparse fast paths in the suite.
-
:material-numeric-11-box:{ .lg .middle } LAPJVsp
The sparse sibling of LAPJV: JV's column reduction + reduction transfer, run on a CSR adjacency and finished by a warm-started sparse SAP — never densifies.