Re:Ask HN: What's your favorite elegant/beautiful algorithm?
by joker3 on Wednesday October 17, 2018 @12:47PM
(#18240901)
There's no matching process at the beginning of medical school, but there is for assigning med school graduates to residencies. This variant of the problem is NP-hard, so there's no exact solution, but matching still works pretty well. https://web.stanford.edu/~alroth/papers/rothperansonaer.PDF has all the details.
[ Parent
| on HN ]
Re:Ask HN: What's your favorite elegant/beautiful algorithm?
by QML on Wednesday October 17, 2018 @05:28PM
(#18243985)
When you are referring to this "variant", are you referring to maximal matching, or bipartite matching when the number of people and schools don't equal?
Re:Ask HN: What's your favorite elegant/beautiful algorithm?
by andreareina on Thursday October 18, 2018 @11:01PM
(#18253972)
Not the parent, but I think they refer to the fact that with admissions, matches are permanent (once a student accepts a school's offer, said offer can't be rescinded), while Gale-Shapely requires provisional pairings until all the rounds have been gone through and a final result is available.