a) Describe an algorithm to produce a stable many-to-many matching for any insta
ID: 3911259 • Letter: A
Question
a) Describe an algorithm to produce a stable many-to-many matching for any instance
of this polygamous marriage problem.
c) Give a small example instance where a man is unmarried at the end of running
your algorithm.
d) Give a proof that at termination of your algorithm, if a man is unmarried, he
cannot possibly have a wife in any stable matching and remains forever alone.
Suppose we have n men and n women, where the men propose to the women. Each man mi has a preference list containing the n women, and a number 0?km,Explanation / Answer
1-make two N*N sized two dimensinal array one for men one for women
2-take one N sized one di
3-take count as 0//for counting how much men get married
4-for(i=0;i<N;i++)
{
s=0;
for(j=0;j<N;j++)
{
if(M[i][j]==1 && W[j][i]==1 && a[i]-->0)
s=1;
}
if(s==1)
count++;
}
5-now your required unmarried mens are (N-count)
6-for eg take M[][]={{1,0,1,0},{1,1,0,0},{1,0,1,1},{1,0,0,0}} W[][]={{1,0,0,0},{1,0,1,0},{1,0,1,1},{1,0,1,1}} a[]={1,1,1,1} here (2,3) remains unmarried
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.