In the class we showed that the number of iterations (number of proposals) in the Gale-Shapley...

Transcribed Image Text:

In the class we showed that the number of iterations (number of proposals) in the Gale-Shapley algorithm is upper bounded by < n² for n men and n women, since each man can only make ≤ n proposals. However, we haven't shown a lower bound on number of iterations. To show the lower bound is also in the order of n², please give a way to construct the preference lists for n men and n women such that the Gale-Shapley algorithm will run for (n²) iterations. (For simplicity, you can assume that the algorithm always chooses the unmatched man with the smallest index at each iteration). In the class we showed that the number of iterations (number of proposals) in the Gale-Shapley algorithm is upper bounded by < n² for n men and n women, since each man can only make ≤ n proposals. However, we haven't shown a lower bound on number of iterations. To show the lower bound is also in the order of n², please give a way to construct the preference lists for n men and n women such that the Gale-Shapley algorithm will run for (n²) iterations. (For simplicity, you can assume that the algorithm always chooses the unmatched man with the smallest index at each iteration).

Answer rating: 100% (QA)

Lower Bound n Iterations The GaleShapley algorithm is a classic algorithm for solving the stable marriage problem where n men and n women each have a ... View the full answer