Problem Detail: Let us say you have a group of guys and and a group of girls. Each girl is either attracted to a guy or not, and vice versa. You want to match as many people as possible to a partner they like. Does this problem have a name? Is it feasibly solvable? Sounds hard to me… Ps. note that since the attraction is not neccessarily mutual the standard max-flow solution does not work.
Asked By : The Unfun Cat
Answered By : A.Schulz
I think it is still the standard bipartite maximum matching problem, which can be solved by the algorithm of Hopcroft and Karp. You put an edge in the bipartite boys-girls graph, iff you have mutual attraction. Then you maximize your matching and voilà. Notice that if you would never assign a boy to a girl with one-sided attraction, since this does not increase you objective function (# of mutal attractions). If you want to maximize the number of happy people, then you set the weights of the complete bipartite boys-girls graph as follows
- mutual attraction = 2 happy people
- one sided attraction = 1 happy people
- otherwise = 0 happy people
You then can compute the maximum weighted bipartite matching.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/6807 Ask a Question Download Related Notes/Documents
