Content deleted Content added
Revert: those are not quotes, they are primes. An ASCII apostrophe at least might show up primelike for some readers; quotes never should. |
→Similar problems: Added stable roommates problem and hospitals/residents problem (with or without couples) |
||
Line 46:
== Similar problems ==
The '''[[weighted matching problem]]'''
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]].<ref>Gusfield and Irving, ''The Stable Marriage Problem: Structure and Algorithms,'' p. 54; MIT Press, 1989.</ref>
==References==
| |||