Description Usage Arguments Details Value Author(s) References Examples

Solve the linear sum assignment problem using the Hungarian method.

1 | ```
solve_LSAP(x, maximum = FALSE)
``` |

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

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
*∑_{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).

An object of class `"solve_LSAP"`

with the optimal assignment of
rows to columns.

Walter Böhm [email protected] kindly provided C code implementing the Hungarian method.

C. Papadimitriou and K. Steiglitz (1982),
*Combinatorial Optimization: Algorithms and Complexity*.
Englewood Cliffs: Prentice Hall.

1 2 3 4 5 6 | ```
x <- matrix(c(5, 1, 4, 3, 5, 2, 2, 4, 4), nrow = 3)
solve_LSAP(x)
solve_LSAP(x, maximum = TRUE)
## To get the optimal value (for now):
y <- solve_LSAP(x)
sum(x[cbind(seq_along(y), y)])
``` |

```
Optimal assignment:
1 => 3, 2 => 1, 3 => 2
Optimal assignment:
1 => 1, 2 => 2, 3 => 3
[1] 5
```

clue documentation built on April 23, 2018, 5:04 p.m.

Embedding an R snippet on your website

Add the following code to your website.

For more information on customizing the embed code, read Embedding Snippets.