I have to design a student-job placement algorithm. The problem statement is :

Let there be two sets - one set of jobs $J = \{j_1, j_2, j_3 .... j_m\}$ and other set of students $S = \{s_1, s_2, s_3 .... s_n\}$ with $n \ge m$.

Each job $j_i$ has its priority list (ranked list) of students and each student $s_i$ has its priority list (ranked list) of jobs.

I have to create a matching in the bipartite graph of J and S as : $ M= \{ (s_{i_1},j_{k_1}), (s_{i_2},j_{k_2}), (s_{i_3},j_{k_3})....(s_{i_m},j_{k_m}) \} $ with the following constraints :

  • Each job must be matched with exactly 1 student, i.e the matching M should be J-saturated with each job getting only 1 student.

  • There should be no unstable pairs, i.e there should be no pairs in M like $ (s_i,j_i) $ and $ (s_k,j_k) $ where $ s_i $ prefers $ j_k $ over $ j_i $ and simultaneously $ j_k $ prefers $ s_i $ over $ s_k $. In other words, all the priority lists of students and jobs must be followed.

  • Let the rank of a student selected in a job $ j_i $ in its priority list be $ r_i $ and so for each student $ s_i $, the rank of the job which he/she gets in his/her priority list be $ t_i $. For a student who does not get a job, $ t_i $ would be one more than the length of that student's priority list. Let $ w_1 $ and $ w_2 $ be constants. The constraints here are :

    • $ w_1 \sum_{i=1}^m r_i $ + $ w_2 \sum_{i=1}^n t_i $ should be minimized so that both jobs and students are happy with the allocation (matching M).

    • $ w_1 $ + $ w_2 $ = $1$ and they both are constants. A simple particular case would be $ w_1 $=$ w_2 $=$0.5$

Please help me design this kind of a combinatorial algorithm which would make both students and jobs happy by giving both of their priority list some predefined weightage.

Thank you in advance.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.