clue (version 0.1-0)

solve-LSAP: 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 square matrix with nonnegative entries.

maximum

a logical indicating whether to minimize of maximize the sum of assigned costs.

Value

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

Details

If $n$ is the number of rows and columns of x, solve_LSAP finds a permutation p of the numbers from 1 to $n$ such that $\sum_{i=1}^n x[i, p[i]]$ is minimized or maximized.

This permutation 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

x <- matrix(c(5, 1, 4, 3, 5, 2, 2, 4, 4), nr = 3)
solve_LSAP(x)
solve_LSAP(x, max = TRUE)