Enchom's blog

Hungarian algorithm
By Enchom, history, 9 years ago, In English

Hello everybody,

Just now I learned max-flow-min-cost algorithms and of course, my first thought was "great, now I don't have to know the Hungarian to solve the assignment problem", but then I stumbled upon the sentence "the Hungarian algorithm solves the assignment problem much faster".

So I looked around the web for good explanation and I found about a couple of thousand links to this Topcoder article, however for some reason it is not working for me. I do not know if it's a problem on my side or the article is just taken down.

I wanted to ask if somebody has the article saved or perhaps has another good article on the Hungarian algorithm with possibly both O(N^4) and O(N^3) complexities explained.

Thanks :)

  • Vote: I like it
  • +25
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Site is down but google has cashe: link

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks, that's what I was looking for :)

    → Reply
»
9 years ago, # |
  Vote: I like it +8 Vote: I do not like it

One of the fails connected with TC jumping the shark... ehm, upgrading the website is that some things, including the tutorials, vanished.

I don't think it's such a big loss — I've never used the Hungarian algorithm before, Ford-Fulkerson has been sufficient in all but one case (some problem on CC Long, where I googled and copypasted something better). Usually, when Ford-Fulkerson in O(N3) fails, then Ford-Fulkerson in O(NM) works, and when even that TLEs, then adding break conditions usually works. The most desperate attempts involve picking flows greedily, more break conditions and replacing BFS by DFS (seriously, why did I start implementing it with BFS?...).

Btw by saying you just learned mincost-maxflow algorithms, you mean the ones strictly more advanced than Ford-Fulkerson, right?

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 3   Vote: I like it +8 Vote: I do not like it

    Eh, I'm not sure what you mean by "Ford-Fulkerson", as far as I know the Ford-Fulkerson algorithm is for regular maximum flow and is the simplest one.

    I read and understood, again from topcoder, the Cycle-Cancelling, Successive shortest path and Primal-Dual. And as far as I know, you can get O(N^3)/O(NM) with the Successive shortest path algorithm. Assuming that's what you mean by "Ford-Fulkerson" then I doubt I learned something strictly more advanced, I just didn't know any approach of solving the min-cost-max-flow before reading about it :P

    P.S.

    There was a problem that used the idea of Hungarian algorithm and not the algorithm itself in a Bulgarian competition, so I thought it'd be nice to know how it works even if I don't use it only for the assignment problem.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Ford-Fulkerson is really the simplest one.

      Cycle-Cancelling, Successive shortest path and Primal-Dual

      I don't know any of these terms :D. There's the typical part of splitting each edge into two directed ones whose sum of flows is the same, then while true: find a path to take non-zero flow through from the source to the sink (BFS or DFS), push that flow over that path. The coding part is trivial, the thinking part only requires proving optimality.

      → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      But you solved 512C - Fox And Dinner, in contest to boot. That's just observation + matching/flows.

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        I know how to solve maximum flow, but I didn't know maximum-flow-minimum-cost.

        Ford-Fulkerson is for regular flow, and is the one in which you use DFS to find the path. If you use BFS then it's called Edmonds-Karp, which is essentially and implementation of Ford-Fulkerson's method.

        However when you add the minimum-cost thingy, other algorithms need to be used and the assignment problem is an example where flow without cost wouldn't be enough. That's why I meant that I'm not sure why you are speaking about "Ford-Fulkerson", since it's an algorithm for regular flow, and not costed one :)

        → Reply
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Oh, you meant that one. I don't really read beyond maxflow-min...

          I did encounter it once, in the past CF ACM trainings. Two solutions in contest, one of them by tourist. I don't think I have to worry about that type of problems :D (when I encounter it, prewritten code should work well enough)

          → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      "There was a problem that used the idea of Hungarian algorithm and not the algorithm itself in a Bulgarian competition, so I thought it'd be nice to know how it works even if I don't use it only for the assignment problem."

      I know this post is very old, but do you happen to remember where exactly the problem appeared and/or have links to it? I studied the Hungarian algorithm recently and am curious to know.

      → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    "Btw by saying you just learned mincost-maxflow algorithms, you mean the ones strictly more advanced than Ford-Fulkerson, right?"

    I don't know any flow algorithms and I can live with it.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +15 Vote: I do not like it

      I know Ford-Fulkersion , Edmond-Carp and Dinic's algorithom to find maximum flow and i am still blue. :P

      Actually in our country most of the coders emphasize more in learning new new algorithms rather than increasing analytical skills.

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
        ← Rev. 2   Vote: I like it +1 Vote: I do not like it

        And also your country has great contributors too like zobayer hasan

        → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Then you haven't solved any maxflow/mincost problems ever? :o

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it +57 Vote: I do not like it

        Never. But I don't consider it as something to be proud of. I'm lazy, that's it.

        → Reply
»
9 years ago, # |
  Vote: I like it +7 Vote: I do not like it

This works: TopCoder: Hungarian Algorithm

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

http://e-maxx.ru/algo/assignment_hungary

https://translate.google.com/translate?hl=ru&sl=ru&tl=en&u=http%3A%2F%2Fe-maxx.ru%2Falgo%2Fassignment_hungary

→ Reply