In social networks ,each person prefers to meet with people from their own commu

Question

In social networks ,each person prefers to meet with people from their own community and are reluctant to switch affiliations. If they switch, they pay a penalty for switching csw and if they visit a meeting of a community different from their own they pay a penalty for visiting cvis . Suppose all the meeting rooms have different colors representing communities. Let there be T time steps 1, ..., T , n people 1, ..., n, and R rooms. Then let a matrix of observed meetings of people in those times be Mij , where mij ? {1, ..., n} is the set of people (which may be empty) that met at time i in room j. For example, the matrix that describes the observations in figure 4.1 is M = [ {1; 2; 3} {4} {5} {1; 3} {2; 4} {5} {1; 3} {4} {2; 5} {1; 3} {4} {2; 5} {1; 3; 4} {2; 5} ] Given the M matrix and the penalties csw and cvis , give a dynamic programming algorithm that assigns a community color to each individual at each time step so that the total sum of all the penalty costs incurred by all the individuals is minimized. You can use the fact that the each person’s contribution to the overall minimum is independent. Prove that fact.

Explanation / Answer

Algorithm goes like this:

cvisFlag= 0 // community switch flag
penalty =0

For each person P[i] in personList
get roomListArray from Matrix for that Person
for each R[i] in the roomListArray
   // starting from i=0
   if ( i== 0)
   // assign the room color to the community color
   then
       P[i].communitycolor = R[i].color
   else if (R[i].value == R[i-1].value)
       // keep the same color as the previous one if there is no chnge in the Room number
       then
       P[i].communitycolor = P[i-1].communitycolor
   else if ( exists(R[i+1]) && (R[i].value == R[i+1].value) && cvisFlag==0)
       // look ahead to see if the future room number is also same so that we can optimize community switch
       then
           cvisFlag= 1
       penalty = penalty+1
           P[i].communitycolor = P[i-1].communitycolor
       else if ( exists(R[i+1]) && (R[i].value == R[i+1].value) && cvisFlag==1)
       then
           penalty = penalty+1;  
           // set the community of the person to the current community
           P[i].communitycolor = R[i].color
           // reset the flag                     
           cvisFlag=0
       else
               penalty = penalty+1
               //keep the same color paying the meeting switch penalty
P[i].communitycolor = P[i-1].communitycolor
                       
                  
print penalty

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.