Problem 1 Given a set of 2n points in a plane, consider a situation where a modi

Question

Problem 1 Given a set of 2n points in a plane, consider a situation where a modified version of the Gale- Shapley algorithm is used to achieve Stable Matching. A point, A, ranks the other 2n 1 points in the increasing order of their Euclidean distances from A. Thus, in the preference list of A, the point which is at a minimum distance from A is ranked first. This approach is followed by each of the 2n points in order to rank the other 2n -1 points on their preference list. All distances are unique. The following pseudo code describes the modified Gale-Shapley algorithm and we also provide a basic description: During each iteration, a free point, proposes to another point based on its own (r's) prefer- ence list. However, an engaged point can break up from its current partner if a point ranked higher in its preference list proposes to it . The total number of points is 2n and is, thus, an even number. Any free point can propose to any of the remaining 2n - 1 points. Algorithm 1 Modified Gale-Shapley algorithm for Stable Matching of points in a plane Initially all p P are free while there is a point that is free and has not proposed to every other point do Choose such a point p Let qE P be the highest ranked point in p's preference list to which P has not yet proposed if q is free then (p, q) become engaged else q is currently engaged to p if (Distance of p from p remains free > (Distance of p' from q) then else (Distance of p from q)

Explanation / Answer

False:

For example let's consider there are 10 q's and 10 p's.

P is free

Initially he need to check among q's which one is near( this was not there in above algorithm)

First p checks among the q which is having less distance or the preferred q among the p's list and then he asks for the proposal.

If q is not paired up with any one they become partners.

Else if q is partner to another p' , q checks the distances between p' and p and picks the optimum one.

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

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