Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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.

share|improve this question
    
Title improvements welcome. Don't feel it is as helpful as could be, but was the best I could come up with. –  The Unfun Cat Nov 21 '12 at 11:05
add comment

1 Answer

up vote 5 down vote accepted

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.

share|improve this answer
    
"You want to match as many people as possible to a partner they like." With this I meant that if A likes B but B does not like A you might possibly still include the A to B edge as it would give you a score of one. If both liked each other that would give you a score of two. I probably did not explain this well enough, very sorry. –  The Unfun Cat Nov 21 '12 at 13:10
    
Ah, there is a weighted version. Thanks. –  The Unfun Cat Nov 21 '12 at 13:21
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.