Weighted bipartite matching?
Moderator: Board moderators
Weighted bipartite matching?
Hi,
I know how to do bipartite matching when edges between sets of vertices are unweighted. What if these edges need to be assigned weights? For example, "reflecting the salary of the employee or their effectiveness at a given task". I know that so called Hungarian method solves this problem, but I'm interested if this problem can be solved using flow algorithms by constructing somewhat more complicated graph. Can anybody help me? Thanks.
I know how to do bipartite matching when edges between sets of vertices are unweighted. What if these edges need to be assigned weights? For example, "reflecting the salary of the employee or their effectiveness at a given task". I know that so called Hungarian method solves this problem, but I'm interested if this problem can be solved using flow algorithms by constructing somewhat more complicated graph. Can anybody help me? Thanks.
Books. Cats. Life's good
Hi,
I'll try to help:)
There are a number of algorithms for minconstmaxflow (and weighted matching). The best (fastest) (as far as I know) is the Hungarian algorithm. However it is very complex and hard to impelement. Well, not "very" complex but hard for me. You can also do mincostmaxflow the same way as you do flow with FordFulkerson based algorithms. You just use the cheapest aug path every time (note: there can be negative weights so you can't use Dijikstra (well, you can but you have to do some modifications)). Another way is to find some maxflow for the network and then push some flow until there are no negative cycles (BellmanFord again...).
If you can't find enough materials on the topic ask for details. I'll be happy to help you.
I'll try to help:)
There are a number of algorithms for minconstmaxflow (and weighted matching). The best (fastest) (as far as I know) is the Hungarian algorithm. However it is very complex and hard to impelement. Well, not "very" complex but hard for me. You can also do mincostmaxflow the same way as you do flow with FordFulkerson based algorithms. You just use the cheapest aug path every time (note: there can be negative weights so you can't use Dijikstra (well, you can but you have to do some modifications)). Another way is to find some maxflow for the network and then push some flow until there are no negative cycles (BellmanFord again...).
If you can't find enough materials on the topic ask for details. I'll be happy to help you.

 Experienced poster
 Posts: 209
 Joined: Sun Jan 16, 2005 6:22 pm
here's one link: http://www.mcs.csuhayward.edu/~simon/ha ... /hall.html
hope it helps.
hope it helps.
Books. Cats. Life's good

 Experienced poster
 Posts: 209
 Joined: Sun Jan 16, 2005 6:22 pm
is it a weighted bipartite graph???
can someone show me to that in 10804, how the third input working??
plz help me!
can someone show me to that in 10804, how the third input working??
plz help me!
Code: Select all
Input:
3 3 0
0 1
1 2
2 1
1 0
1 1
2 0
Output:
Case #3:
1.414
How must we keep alternating trees in the Hungarian Method for Maxweight biparite matching? What's the proper data structure for them? Can someone post here or as PM his/her code for the problem, please?
Thank you.
Thank you.
If there is ever a war between men and machines, it is easy to guess who will start it (c) Arthur Clarke
well, fellows, I'm trying to figure out how the algorithm works forsooth.
Just tracing algorithm instructions by hand over a sample weighted bipartite graph.
If you have something to help me to get the feeling, please post.
Here the Hungarian Method is explained, my questions refer to the things from here:
http://www.cs.ust.hk/mjg_lib/Classes/CO ... atching.ps
Just tracing algorithm instructions by hand over a sample weighted bipartite graph.
If you have something to help me to get the feeling, please post.
Here the Hungarian Method is explained, my questions refer to the things from here:
http://www.cs.ust.hk/mjg_lib/Classes/CO ... atching.ps
If there is ever a war between men and machines, it is easy to guess who will start it (c) Arthur Clarke