The traditional solution for the assignment problem is the Hungarian method - it's complexity is O(V^4) or O(V^3) if using Edmonds method.

However, it can also be reduced to a min cost max flow problem and solved in O(n^3) (by keeping all edges positive and using Dijkstra shortest path).

Why would one use Hungarian method over the flow method?


Actually, the two techniques might actually be basically the same. If you read Schrijver's Combinatorial Optimization: Polyhedra and Efficiency, Section 17.2 (where it talks about the Hungarian method), the description of the method is based on using min-cost augmenting paths, then removing a factor of N by using potentials to obtain nonnegative paths so as to use Dijkstra's algorithm.

In more detail... the traditional weight-altering Hungarian method (e.g. as explained by Wikipedia) is an $O(N^4)$ dual-based algorithm, while Schrijver first explains an $O(N^4)$ primal-based algorithm. He goes on to explain that it can be implemented in $O(N^3)$ time by using potentials so as to use Dijkstra's algorithm in place of Bellman-Ford, obtaining a primal-dual algorithm. However, the $O(N^3)$ dual-based algorithm (e.g., as explained in a sort of confusing way by TopCoder) seems to be doing much of the same thing. I think the shortest paths manifest as looking for the smallest nonnegative cost edge in each iteration.

  • $\begingroup$ Actually, as Schrijver tends to do, he already explains the best insights. This exact correspondence is the subject of section 18.5b, "Dual, primal-dual, primal?" $\endgroup$ – Dave Pritchard Jan 25 '16 at 4:13

I would prefer the Hungarian method in cases, where a simpler algorithm and a simpler data structure seem desirable; that could be the case, if only small instances need to be handled or, if a GPU implementation is intended.

Handling m-to-n assignments is also possible with the Hungarian Method via cloning:

  • if a worker can perform $k$ tasks, then creating $k$ clones of the respective worker does the trick.

  • if a task requires $k$ workers, then creating $k$ clones of the tasks does the trick.

if w.l.o.g. workers correspond to rows in the assignment matrix and tasks to columns, then cloning is done by creating duplicates of the corresponding rows, resp. columns.
It should however be kept in mind, that a solution is not always possible due to shortage of either workers or tasks, but drawing conclusions of such failures (need to hire a worker or send him on vacation or, to create or give up tasks), is a different story.

Actual advice for chosing between the two methods would however better be discussed in a forum dedicated to scientific computing (e.g. http://scicomp.stackexchange.com)

  • $\begingroup$ Thanks! Can the Hungarian method be used if each each node can have more than 1 "assignment"? $\endgroup$ – EugeneMi Oct 30 '14 at 23:55
  • $\begingroup$ @EugeneMi I just added the answer to the multiple assignment problem in an edit to my answer. I hope that is of any help to you. $\endgroup$ – Manfred Weis Oct 31 '14 at 7:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.