Content deleted Content added
→Solutions for constrained problems: comment for 'constrained' question added |
m →Solutions for constrained problems: ..forgot signature |
||
Line 30:
: 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). --[[User:Kraymer|Kraymer]] ([[User talk:Kraymer|talk]]) 14:34, 7 February 2010 (UTC)
== Choices of methaphorical gender ==
| |||