sdo@linus.UUCP (Sean D. O'Neil) (02/14/89)
In article <525@pan> jal@cs.wayne.edu (Jason Leigh) writes: >I am trying to solve the Assignment problem (maximum matching on >minimal weight in a bi-partite graph) using Neural Nets (more specifically >the Boltzmann Machine). Has anyone done this already? Is there a >good way to approach this besides converting the problem to TSP >and then solving that? I just want to make sure you don't really need *any* solution to the Assignment problem, but that you specifically want a neural net solution. If that's not the case, then there are lots of suboptimal methods for solving the Assignment problem that work fairly well that you should check out first. Of course, if you really need an optimal solution, try Munkre's algorithm (see Burgeois and Lassalle in COMMUNICATIONS OF THE ACM, Dec. 1971, pp. 802-806). Then again, if you really needed the optimal solution, you probably wouldn't be thinking about neural nets anyway. For a specific n-net solution, check out proceedings of ICNN and INNS. I'll bet that someone's done this already, probably on a Hopfield net (pardon me, Hopfield-Grossberg net :-). Sean