Stable matching problem: Difference between revisions

Content deleted Content added
Citation bot (talk | contribs)
m Alter: journal. Add: jstor. | You can use this bot yourself. Report bugs here. | Activated by User:AManWithNoPlan | All pages linked from User:AManWithNoPlan/sandbox2 | via #UCB_webform_linked
An "international conference" is unlikely to be a journal and (despite what IEEE says) its acronym is unlikely to be lowercased; url redundant with hdl
Line 88:
* This process is repeated until everyone is engaged.
 
This algorithm is guaranteed to produce a stable marriage for all participants in time <math>O(n^2)</math> where <math>n</math> is the number of men or women.<ref name="IwamaMiyazaki2008">{{cite journalconference|last1=Iwama|first1=Kazuo|author1-link=Kazuo Iwama (computer scientist)|last2=Miyazaki|first2=Shuichi|titlecontribution=A Survey of the Stable Marriage Problem and Its Variants|year=2008|pages=131–136|doi=10.1109/ICKS.2008.7|journaltitle=International Conference on Informatics Education and Research for Knowledge-Circulating Society (IcksICKS 2008)|publisher=IEEE|isbn=978-0-7695-3128-1|hdl=2433/226940|url=https://repository.kulib.kyoto-u.ac.jp/dspace/bitstream/2433/226940/1/ICKS.2008.7.pdf}}</ref>
 
Among all possible different stable matchings, it always yields the one that is best for all men among all stable matchings, and worst for all women.