Rows are added one at a time; each finds a shortest augmenting path in the
reduced costs c_ij - u_i - v_j with dual potentials (Jonker and Volgenant
1987), so the assignment is optimal. A matrix with more rows than columns is
solved on its transpose.
Usage
LinearAssignment(cost, maximize = FALSE)
Arguments
- cost
Finite cost matrix.
- maximize
Maximise instead of minimise.
Value
list(rows, cols (1-based matched pairs, rows ascending), total,
row_potential, col_potential).
References
Kuhn, H. W. (1955). The Hungarian method for the assignment
problem. Naval Research Logistics Quarterly 2, 83-97.
Jonker, R. and Volgenant, A. (1987). A shortest augmenting path algorithm
for dense and sparse linear assignment problems. Computing 38, 325-340.
Examples
LinearAssignment(rbind(c(4, 1, 3), c(2, 0, 5), c(3, 2, 2)))$total
#> [1] 5
