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 \(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).
References
C. Papadimitriou and K. Steiglitz (1982),
Combinatorial Optimization: Algorithms and Complexity.
Englewood Cliffs: Prentice Hall.