1
$\begingroup$

I have a list of companies with n timeslots (number of slots may vary from company to company) and a list of students. Each student made a list of their top 3 companies they would like to talk to.

Is there an algorithm to efficiently match those students to timeslots, taking the student's preferences into account?

I already did some research, and I think I could find some answers in the field of Graph Theory, but I'm really new to this.

Your help would be really appreciated.

Thank you in advance.

Improve this question
$\endgroup$
2
  • $\begingroup$ Can you clarify: Should the solution be of the form that students talk to as many of their top 3 companies as possible or just with one company, ranked as high as possible? $\endgroup$
    – ttnick
    Commented Oct 10, 2022 at 15:06
  • $\begingroup$ @ttnick: thank you for your reply. If possible, one company (as high as possible) should be fine $\endgroup$
    – Sam
    Commented Oct 10, 2022 at 16:35

2 Answers 2

Reset to default
1
$\begingroup$

One approach is to model this as a weighted bipartite matching problem, also known as the assignment problem. This is appropriate if the objective function you're trying to maximize is the sum of "goodness scores" associated with each timeslot that gets filled.

Another approach is to model this as an instance of the stable marriage algorithm. This is appropriate if you're trying to achieve some other goal, namely, that no pair of students or companies would be happier by switching places with each other.

These will give you different solutions that try to achieve different aims.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you very much for your reply, but I'm a bit stuck on modeling the problem as an instance of the stable marriage problem, because not all students rank all of the companies (only 3 of them) and companies do not have a preference-list to do the matching. $\endgroup$
    – Sam
    Commented Oct 10, 2022 at 21:37
0
$\begingroup$

Co-operative Education | University of Waterloo pioneered this kind of thing in the 1960s.

I (and thousands of other students) were paired with all of our top-10 choices for interviews, I don't remember anyone having problems with it, and that was 50 years ago.

They currently handle 7000+ employers. You might talk to someone at UW to see what algorithms they use.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.