## Weighted bipartite matching?

Let's talk about algorithms!

Moderator: Board moderators

hashish
New poster
Posts: 3
Joined: Sat Mar 25, 2006 11:23 am
Location: Lithuania

### 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.
Books. Cats. Life's good

frk_styc
New poster
Posts: 10
Joined: Sun Apr 17, 2005 5:00 pm
weighted bipartite matching can be solved by min-cost max-flow. the method looks quite similar to solving maximum cardinality matching by max-flow.

andresw1
New poster
Posts: 27
Joined: Sat Mar 18, 2006 5:04 pm
Hi,

I'll try to help:)
There are a number of algorithms for min-const-maxflow (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 min-cost-max-flow the same way as you do flow with Ford-Fulkerson 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 max-flow for the network and then push some flow until there are no negative cycles (Bellman-Ford again...).

If you can't find enough materials on the topic ask for details. I'll be happy to help you.

hashish
New poster
Posts: 3
Joined: Sat Mar 25, 2006 11:23 am
Location: Lithuania
Thank you for your help. I'll try to figure out the details myself. The keywords are "min-cost max-flow"
Books. Cats. Life's good

asif_rahman0
Experienced poster
Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm
i know bipartate graph but dont know the algorithm or anything about bipartate matching.

so if someone tell me how can i learn abt bipartate matching???
Or any other link/tutorial. Then it will be better for me to solve problem.

thnx in advance.

hashish
New poster
Posts: 3
Joined: Sat Mar 25, 2006 11:23 am
Location: Lithuania
Books. Cats. Life's good

asif_rahman0
Experienced poster
Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm
thnx hashish

asif_rahman0
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!

Code: Select all

``````Input:
3 3 0
0 1
1 2
2 1
1 0
1 1
2 0
Output:
Case #3:
1.414
``````

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm
asif_rahman must have got #10804 by now , so I only want The Hungarian Algorithm for max-weight biparite matching to be explained from a contestant's point of view.

thank you,
serur
If there is ever a war between men and machines, it is easy to guess who will start it (c) Arthur Clarke

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm
How must we keep alternating trees in the Hungarian Method for Max-weight 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.
If there is ever a war between men and machines, it is easy to guess who will start it (c) Arthur Clarke

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm
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
If there is ever a war between men and machines, it is easy to guess who will start it (c) Arthur Clarke