A fine example

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

ALGORITHM
linear programming optimization

Archive