solve_LSAP: Solve Linear Sum Assignment Problem

Description

Solve the linear sum assignment problem using the Hungarian method.

Usage

solve_LSAP(x, maximum = FALSE)

Value

An object of class "solve_LSAP" with the optimal assignment of rows to columns.

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.

Author

Walter Böhm Walter.Boehm@wu.ac.at kindly provided C code implementing the Hungarian method.

Details

If $n r$ and $n c$ 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 $n r$ to the numbers from 1 to $n c$ (a permutation of these numbers in case x is a square matrix) such that $\sum_{i = 1}^{n r} 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).

References

C. Papadimitriou and K. Steiglitz (1982), Combinatorial Optimization: Algorithms and Complexity. Englewood Cliffs: Prentice Hall.

Examples

Run this code

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)])

Run the code above in your browser using DataLab

Last chance! 50% off unlimited learning