# solve_LSAP: Solve Linear Sum Assignment Problem In clue: Cluster Ensembles

## Description

Solve the linear sum assignment problem using the Hungarian method.

## Usage

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

## Arguments

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

## Details

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

## Value

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

## Author(s)

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

## References

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

## Examples

 ```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)]) ```

### Example output

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

clue documentation built on Sept. 10, 2018, 9:04 a.m.