WisFaq!

Slechtste partner in Gale Shapley

Beste,

Gegeven is het stable marriage algoritme van Gale Shapley. Claim: Het algoritme matcht elke vrouw met haar slechtst mogelijk partner. In slide 24 van https://ocw.tudelft.nl/wp-content/uploads/Algoritmiek_Stable_Matching__continued_.pdf staat in de tweede regel van het bewijs dat er een matching S' bestaat met een eigenschap. Hoe weten we zo zeker dat S' moet bestaan met die eigenschap? Ik zie niet uit welke aanname dat volgt.

Vriendelijke groet,

Nico

Nico
11-2-2022

Antwoord

Dat volgt uit de definitie van "valid partner" eerder op de slides.
Op slide 25 staat een verwijzing naar het cursusboek (links onderaan). Dat boek is online te bekijken, zie hieronder, en dus in het bijzonder pagina's 11 en 12.

Het boek geeft wat meer uitleg dan de slides.

Zie Boek: Algorithm Design [https://ict.iitk.ac.in/wp-content/uploads/CS345-Algorithms-II-Algorithm-Design-by-Jon-Kleinberg-Eva-Tardos.pdf]

kphart
11-2-2022