LAPJV: Solve linear assignment problem using LAPJV

In TreeDist: Calculate and Map Distances Between Phylogenetic Trees

Solve linear assignment problem using LAPJV

Description

Use the algorithm of \insertCiteJonker1987;textualTreeDist to solve the Linear Sum Assignment Problem (LSAP).

Usage

LAPJV(x)

Arguments

x	Matrix of costs.

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 \insertCiteMunkres1957TreeDist, which is implemented in clue::solve_LSAP().

Note: the JV algorithm expects integers. In order to apply the function to a non-integer n, as in the tree distance calculations in this package, each n is multiplied by the largest available integer before applying the JV algorithm. If two values of n exhibit a trivial difference – e.g. due to floating point errors – then this can lead to interminable run times. (If numbers of the magnitude of billions differ only in their last significant digit, then the JV algorithm may undergo billions of iterations.) To avoid this, integers over 2^22 that differ by a value of 8 or less are treated as equal.

Value

LAPJV() returns 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.

Author(s)

C++ code by Roy Jonker, MagicLogic Optimization Inc. [e-mail], with contributions from Yong Yang [e-mail], after Yi Cao

References

\insertAllCited

See Also

Implementations of the Hungarian algorithm exist in adagio, RcppHungarian, and clue and lpSolve; for larger matrices, these are substantially slower. (See discussion at Stack Overflow.)

The JV algorithm is implemented for square matrices in the Bioconductor package GraphAlignment::LinearAssignment().

Examples

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

LAPJV(problem)

TreeDist documentation built on Sept. 11, 2024, 9:10 p.m.