News for hackers. Stuff that matters.
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.
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.
Re:Ask HN: What's your favorite elegant/beautiful algorithm? by joker3 on Saturday October 20, 2018 @05:45PM (#18265662)
The issue is that couples want to be placed together. That makes everything trickier than if people just placed independently.