Faster alternatives to the Hungarian Algorithm?

Question

I've successfully implemented Munkres' variation of the assignment algorithm in C#, the Hungarian Algorithm, as seen here https://users.cs.duke.edu/~brd/Teaching/Bio/asmb/current/Handouts/munkres.html

I was disappointed to find that it is a fairly slow algorithm the more agents you have, although a very very accurate one. So i was wondering if there's a way to sacrifice it's accuracy for performance? Or is there an alternative algorithm whose steps i can follow?

Ive seen a bunch of academic papers but i don't know what 90% of those words mean, so if anyone knows a comprehensive step by step to an alternative, it would help me out a lot in my current project. Thank you.

Units being assigned a yellow waypoint. One to one assignment.

Answer 1

The Hungarian algorithm is antiquated (IMO) and basically sees no interest or research that improves it.

This is largely because anything the Hungarian algorithm can solve is solvable by modelling on the appropriate graph and applying the proper algorithm.

In most cases, what you actually want to use is the Minimum Cost (Maximum) Flow algorithm. MCF is actively researched and has seen many improvements in the last decade or so.

There are several off-the-shelf software that solve these problems efficiently, that people have put in significant effort to optimize. I doubt you will perform better than these without spending months to years optimizing your own code.

Check out

• https://lemon.cs.elte.hu/trac/lemon
• https://developers.google.com/optimization/flow/mincostflow

Along with a myriad of other tools/libraries that can be used to solve this problem efficiently.

Don't reinvent the wheel unless you have a compelling reason to!

Conveniently, google-or has documentation on how to interpret assignment problems as instances of MCF: https://developers.google.com/optimization/flow/assignment_min_cost_flow