Module matching_lsap 

Linear Sum Assignment Problem (ALGO-MA-005) — Hungarian method.

Counterpart of igraph_solve_lsap in references/igraph/src/internal/lsap.c:664.

Solves the balanced assignment problem: given an n×n cost matrix, find a permutation p such that Σ C[i][p[i]] is minimized.

Algorithm

Classical Hungarian method (Kuhn-Munkres): O(n³).

1. Subtract row and column minima (preprocessing).
2. Greedily assign zeros.
3. Iteratively cover rows/columns and reduce until all rows assigned.

Functions

solve_lsap

Solve a balanced linear sum assignment problem (Hungarian method).