LinearAssignment: Solve linear assignment problem

In GraphAlignment: GraphAlignment

Description

Solve the linear assignment problem specified by the cost matrix.

Usage

LinearAssignment(matrix)

Arguments

matrix

cost matrix

Details

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

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

Author(s)

Joern P. Meier, Michal Kolar, Ville Mustonen, Michael Laessig, and Johannes Berg

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

Example output

           [,1]       [,2]       [,3]       [,4]        [,5]
[1,]  1.9361372  0.4799021  1.2529215  0.0323784  0.06418556
[2,] -2.6065505  1.5668487 -0.7452492  0.0750315 -0.01817436
[3,]  0.1017669 -0.4144199 -0.2252630 -0.9694327 -0.37202021
[4,]  0.4829084 -1.6126931  0.4616213  0.7664048  0.28469562
[5,] -0.7961925 -0.1486903  0.3760055 -0.1566079  0.45359655

GraphAlignment documentation built on Nov. 8, 2020, 6:56 p.m.