Similar Problems
The weighted matching problem seeks to find a matching in a weighted bipartite graph that has maximum weight. Maximum weighted matchings do not have to be stable, but in some applications a maximum weighted matching is better than a stable one.
The stable roommates problem is similar to the stable marriage problem, but differs in that all participants belong to a single pool (instead of being divided into equal numbers of "men" and "women").
The hospitals/residents problem — also known as the college admissions problem — differs from the stable marriage problem in that the "women" can accept "proposals" from more than one "man" (e.g., a hospital can take multiple residents, or a college can take an incoming class of more than one student). Algorithms to solve the hospitals/residents problem can be hospital-oriented (female-optimal) or resident-oriented (male-optimal).
The hospitals/residents problem with couples allows the set of residents to include couples who must be assigned together, either to the same hospital or to a specific pair of hospitals chosen by the couple (e.g., a married couple want to ensure that they will stay together and not be stuck in programs that are far away from each other). The addition of couples to the hospitals/residents problem renders the problem NP-complete.
Read more about this topic: Stable Marriage Problem
Famous quotes containing the words similar and/or problems:
“A whole village-full of sensuous emotion, scattered abroad all the year long, surged here in a focus for an hour. The forty hearts of those waving couples were beating as they had not done since, twelve months before, they had come together in similar jollity. For the time Paganism was revived in their hearts, the pride of life was all in all, and they adored none other than themselves.”
—Thomas Hardy (1840–1928)
“If combat means living in a ditch, females have biological problems staying in a ditch for 30 days because they get infections.... Males are biologically driven to go out and hunt giraffes.”
—Newt Gingrich (b. 1943)