3
$\begingroup$

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.

$\endgroup$

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.