do_lap | R Documentation |
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.
do_lap(score, method = "clue")
score |
matrix of pairwise scores |
method |
One of "lapjv", "lapmod", or "clue" |
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.
do_lap
returns a vector which indicates the
best matching column for each row.
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.
set.seed(12345)
cost <- Matrix::rsparsematrix(10, 10, .5)
cbind(
do_lap(cost, "lapjv"),
do_lap(cost, "lapmod"),
do_lap(cost, "clue")
)
Add the following code to your website.
For more information on customizing the embed code, read Embedding Snippets.