Gitt en Bipartitt graf med menn og kvinner, hvor kvinnene og mennene en har rangering av hvor “desirable” alle av de motsatte kjønn er, finn den beste matchingene. Dersom en mann og kvinne ønsker hverandre mest, men er fanget i andre forhold, skaper de en såkalt “blocking pair”, noe som gjør at den ikke lenger er en Stable matching algorithms.
Wikipedia artikkel Youtube Video
Er “nesten” grådig. Vi tar lokalt optimale valg, men valgene er ikke bindene.
Matching basert på ønskelister
