GraphAlignment (version 1.36.0)

LinearAssignment: Solve linear assignment problem

Description

Solve the linear assignment problem specified by the cost matrix.

Usage

LinearAssignment(matrix)

Arguments

matrix

cost matrix

Value

The return value is a permutation vector equal to the solution of the linear assignment problem specified by the cost matrix. The result is the permutation P for which MP is minimal (where M is the cost matrix).

Details

This function solves the linear assignment problem defined by the input matrix. [Jonker, Volgenant 1987]

References

Jonker, R & Volgenant, A. (1987) Computing 38, 325--340.

Examples

  m <- matrix(rnorm(25), 5, 5)
  px <- LinearAssignment(round(-1000 * (m / max(abs(m)))))
  m[px,]