by Yubo "Paul" Yang

# Linear Sum Assignment

The Linear Sum Assignment Problem (LSAP) is a combinatoric optimization problem with many practical applications. An elegant solution was proposed in 1955 by Kuhn and lovingly dubbed "The Hungarian algorithm". This polynomial-scaling algorithm is sometimes credited as the predecessor to primal-dual linear programming approaches.

## Presentation Summary

In these slides, I present:

- Definition and examples of the linear assignment problem.
- A polynomial-scaling solution: the Hungarian algorithm.

## Examples

- lsap-kuhn-hung.tgz: “a_dev” contains a simple implementation of the Hungarian algorithm along with visualization. “b_time” is a snakemake folder that measures execution time.

## References

### All Linear Programming

Yubo "Paul" Yang ALGORITHM

linear programming optimization