Weighted bipartite matching?

Let's talk about algorithms!

Moderator: Board moderators

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

Weighted bipartite matching?

Post by hashish » Sat Mar 25, 2006 11:33 am

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

Post by frk_styc » Sat Mar 25, 2006 11:27 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

Post by andresw1 » Sun Mar 26, 2006 12:58 am

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

Post by hashish » Sun Mar 26, 2006 9:19 pm

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

Post by asif_rahman0 » Sun Apr 02, 2006 11:17 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

Post by hashish » Sun Apr 02, 2006 11:31 pm

Books. Cats. Life's good ;)

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

Post by asif_rahman0 » Mon Apr 03, 2006 6:19 pm

thnx hashish

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

Post by asif_rahman0 » Tue Jun 13, 2006 9:21 am

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

Post by serur » Mon Nov 27, 2006 2:28 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

Post by serur » Tue Nov 28, 2006 9:42 am

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

Post by serur » Tue Nov 28, 2006 10:05 am

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

Post Reply

Return to “Algorithms”