TreeDist (version 1.1.1)

LAPJV: Solve linear assignment problem using LAPJV

Description

Use the algorithm of Jonker & Volgenant (1987) to solve the Linear Sum Assignment Problem.

Usage

LAPJV(x)

Arguments

x

Square matrix of costs.

Value

A list with two entries: score, the score of the optimal matching; and matching, the columns matched to each row of the matrix in turn.

Details

The Linear Assignment Problem seeks to match each row of a matrix with a column, such that the cost of the matching is minimized.

The Jonker & Volgenant approach is a faster alternative to the Hungarian algorithm (Munkres 1957), which is implemented in clue::solve_LSAP().

NB. At present, only square matrices are supported; if you need support for non-square matrices, drop a note at issue #25 and I'll prioritize development.

References

Jonker1987TreeDist

Munkres1957TreeDist

Examples

# NOT RUN {
problem <- matrix(c(7, 9, 8, 9,
                    2, 8, 5, 7,
                    1, 6, 6, 9,
                    3, 6, 2, 2), 4, 4, byrow=TRUE)

LAPJV(problem)
# }