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:
“Let the day perish wherein I was born, and the night in which it was said, There is a man child conceived.”
—Bible: Hebrew Job, 3:3.
A similar imprecation is found in Jeremiah 20:14-15.
“The problems of all of humanity can only be solved by all of humanity.”
—Friedrich Dürrenmatt (1921–1990)