>> Well, the hungarian algorithm has a theoretical upper bound of O(n^3), >> with n being the number of nodes, which is pretty much the best you >> can do if you have a dense graph and make no assumptions on >> capacities. > > OK, your input is making my motivation to fight with Jonker-Volgenant go > down. I'll see with the other people involved if we still target > Jonger-Volgenant, or if we stick with the hungarian algorithm, in which > case the problem is solved.
I'd do that route. From my (somewhat anecdotal) observations, a well coded version of the Hungarian algorithm will beat moderately well-coded implementations of other algorithms on most common types of problems; the data structures in other algorithms are harder to get right. Also, they often tend to show their strengths only on sufficiently large problems. I'd guess that for a speed up, your time would be better spent profiling and maybe cythoning your current implementation of the Hungarian algorithm (also note that there's a few bsd/mit C++ implementations floating around, check the wikipedia page). > >> Hope that answers your questions :-). > > It does. Thanks a lot, it is very useful to have expert knowledge > available. Well, I don't know if I'm an "expert" in this area, but I rub shoulders with a few and I'm glad to be of help. -- Hoyt ++++++++++++++++++++++++++++++++++++++++++++++++ + Hoyt Koepke + University of Washington Department of Statistics + http://www.stat.washington.edu/~hoytak/ + hoy...@gmail.com ++++++++++++++++++++++++++++++++++++++++++ _______________________________________________ NumPy-Discussion mailing list NumPy-Discussion@scipy.org http://mail.scipy.org/mailman/listinfo/numpy-discussion