The Assignment Problem and the Hungarian Method (2005) [pdf] | Hacker News Reader

The Assignment Problem and the Hungarian Method (2005) [pdf]

math.harvard.edu

39 pointsvinchuco9 comments

http://zafar.cc/2017/7/19/hungarian-algorithm/

Article above describes a very short implementation of the most efficient form of the algorithm (40 lines of code).

One interesting use of the Hungarian algorithm is in git-tbdiff [1] (topic branch diff). It uses it to compute which patch in an older topic branch match each patch in a newer topic branch.

[1] https://github.com/trast/tbdiff/blob/master/README.md

For those who learned point set topology from Munkres's book, you may be interested to know that this is also sometimes called the Munkres algorithm: https://en.wikipedia.org/wiki/Hungarian_algorithm .

I recently used this algorithm in a project. For anyone looking for a high-quality Java or Clojure implementation, I would recommend:

https://github.com/timothypratley/munkres (Clojure)

Which wraps:

https://github.com/kevin-wayne/algs4 (Java)

Can somebody explain the reasoning behind step 5?

It's clear that the algorithm works (assuming it converges), because it only uses manipulations that preserve optimality. Why, though, should I choose these manipulations instead of others that also preserve optimality?

You are simply making another zero (because you don't have enough to cover all rows and columns) without making any other cell negative. If you subtracted from uncovered columns and added to covered rows you would get the exact same result. Every uncovered cell is subtracted from and every line crossing is added to.

The only arbitrariness is in the selection of covering rows and columns. There I guess the argument is that if a cell has another zero on its row and another zero on its column (i.e. a line crossing in any possible covering) then it is not going to be in the optimal solution.

Anybody have a year for this?

Based on the parent url and content I think it's 2005:

http://www.math.harvard.edu/archive/20_spring_05/

Thanks!

Reply on news.ycombinator.com