Yes this is classicalproblem, it can be reduced to Min-cost max-flow. But there are other algorithms. you can find answer here http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=hungarianAlgorithm
http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=minimumCostFlow1 2009/3/19, libicocco <libico...@gmail.com>: > > > Dear All, > > I have a problem which i'm sure more people have think about before, > but i can't find any solution around. > I want to select 1 element per row and 1 element per column in a > matrix, and that this set of elements has minimum sum. The application > is, for example, matching of features: given a distance matrix, i want > the matches (pairs of features) that give me minimum sum of distances. > > Any idea? > > PS.- the matrices can be non-square; in that case there will be one > dimension not completely covered with the matches. > > > > --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
