| solve_LSAP {clue} | R Documentation |
Solve Linear Sum Assignment Problem
Description
Solve the linear sum assignment problem using the Hungarian method.
Usage
solve_LSAP(x, maximum = FALSE)
Arguments
x |
a matrix with nonnegative entries and at least as many columns as rows. |
maximum |
a logical indicating whether to minimize of maximize the sum of assigned costs. |
Details
If nr and nc are the numbers of rows and columns of
x, solve_LSAP finds an optimal assignment of rows
to columns, i.e., a one-to-one map p of the numbers from 1 to
nr to the numbers from 1 to nc (a permutation of these
numbers in case x is a square matrix) such that
\sum_{i=1}^{nr} x[i, p[i]] is minimized or maximized.
This assignment can be found using a linear program (and package
lpSolve provides a function lp.assign for doing so), but
typically more efficiently and provably in polynomial time
O(n^3) using primal-dual methods such as the so-called Hungarian
method (see the references).
Value
An object of class "solve_LSAP" with the optimal assignment of
rows to columns.
Author(s)
Walter Böhm Walter.Boehm@wu.ac.at kindly provided C code implementing the Hungarian method.
References
C. Papadimitriou and K. Steiglitz (1982), Combinatorial Optimization: Algorithms and Complexity. Englewood Cliffs: Prentice Hall.
Examples
x <- matrix(c(5, 1, 4, 3, 5, 2, 2, 4, 4), nrow = 3)
solve_LSAP(x)
solve_LSAP(x, maximum = TRUE)
## To get the optimal value (for now):
y <- solve_LSAP(x)
sum(x[cbind(seq_along(y), y)])