Solve the linear assignment problem using the Jonker-Volgenant
algorithm. This is the core optimization step in CytoSPACE.
Usage
solve_lap(cost_matrix, maximize = FALSE)
Arguments
- cost_matrix
A numeric matrix of costs. For rectangular matrices,
the number of rows must be less than or equal to columns.
- maximize
Logical. If TRUE, maximize instead of minimize.
Default is FALSE.
Value
An integer vector of column assignments. The i-th element indicates
which column is assigned to row i (1-indexed).
Details
The Jonker-Volgenant algorithm is an efficient O(n^3) algorithm for solving
the linear assignment problem. It is particularly well-suited for dense
cost matrices.
For rectangular matrices where rows < columns, the algorithm pads the matrix
with dummy rows and returns only the assignments for the original rows.
References
Jonker, R., & Volgenant, A. (1987). A shortest augmenting path algorithm for
dense and sparse linear assignment problems. Computing, 38(4), 325-340.
Examples
if (FALSE) { # \dontrun{
# Create a simple cost matrix
cost <- matrix(c(1, 2, 3, 2, 4, 6, 3, 6, 9), nrow = 3, byrow = TRUE)
# Solve the assignment problem
assignment <- solve_lap(cost)
} # }