iGraphMatch (version 2.0.5)

do_lap: Linear (sum) assignment problem

Description

Compute the best bipartite matching using one of three methods. For an n x n score matrix it find \(\max_{v\in \Pi_n} \sum_{i=1}^n score_{i, v(i)}\) where \(\Pi_n\) denotes all permutations on n objects.

Usage

do_lap(score, method = "clue")

Value

do_lap returns a vector which indicates the best matching column for each row.

Arguments

score

matrix of pairwise scores

method

One of "lapjv", "lapmod", or "clue"

Details

Solves a linear assignment using one of three methods. "clue" uses solve_lsap from the clue package. "lapjv" uses the Jonker-Volgenaut approach implemented in this package. "lapmod" use a modification of JV that exploits sparsity in the score matrix.

Scores do not need to be non-negative. For "clue" the scores are pre-translated to be non-negative which preserves the LAP solution.

References

R. Jonker, A. Volgenant (1987). A shortest augmenting path algorithm for dense and sparse linear assignment problems. Computing, pages 325-340.

A. Volgenant (1996). Linear and Semi-Assignment Problems: A Core Oriented Approach. Computer Ops Res., pages 917-932.

C. H. Papadimitriou and K. Steiglitz (1998). Combinatorial Optimization: Algorithms and Complexity. Courier Corporation.

Examples

set.seed(12345)
cost <- Matrix::rsparsematrix(10, 10, .5)
cbind(
 do_lap(cost, "lapjv"),
 do_lap(cost, "lapmod"),
 do_lap(cost, "clue")
)