Talk:Stable matching problem: Difference between revisions

Revision as of 14:06, 7 February 2010

Revision as of 14:19, 7 February 2010

Line 28:

Anybody know if there are computationally feasible algorithms for solving marriage problems with constraints, e.g. "Is there any stable pairing that matches Alice with Bob and Claire with Dave?" [[User:Henning Makholm|Henning Makholm]] 20:17, 15 October 2006 (UTC)

*: Your example is still just the Stable Marriage problem, using a list that excludes Alice, Bob, Claire and Dave. [[User:Tom Duff|Tom Duff]] 01:56, 25 October 2006 (UTC)

:: Not quite. Alice and Bob might not be each other's first choice, but their marriage needs to remain stable given the pairings we find for the rest of the people. In particular, each man that Alice likes better than Bob needs to be paired with a woman he likes better than Alice, ''and'' each woman that Bobs likes better than alice must be paired with a man she likes better than Bob. One can construct examples where this combined condition holds neither for the male-optimal nor for the female-optimal pairing of for the rest ignoring Alice and Bob, but still is possible for some ''third'' stable pairing. [[User:Henning Makholm|Henning Makholm]] 14:05, 26 October 2006 (UTC)

::: So couldn't you just exclude the four persons, do the GS algorithm and then check if the pairings are still stable? Computationally, that would still be in O(m*n).

== Choices of methaphorical gender ==