Homework Help is Here – Start Your Trial Now!
Engineering
Computer Science
1. Consider the generalization of stable matching problem where a certain man-woman pairs are forbidden. The set of forbidden pairs is denoted as F. Each man m ranks all the woman w for which (m, w) ¢ F and each woman w ranks all the man m for which (m, w) ¢ F. Consider the following algorithm for finding a stable matching that consists of only unforbidden pairs: Initially all m E M and w e W are free; S = Ø While there is a man m who is free and hasn't proposed to every woman w for which (m,w) ¢ F Choose such a man m Let w be the highest-ranked woman in m's preference list to which m has not yet proposed If w is free: Add (m, w) to solution S Else (w is current matched with m'): If w prefers m' to m m remains free Else Replace (m', w) by (m, w) in S Return solution S Answer true or false for the following questions: (a) Any woman w remains engaged from the point at which she receives her first proposal, and the se- quence of partners to which she is engaged get better and better. (b) If a man m is free at the end of the algorithm, then he must have proposed to every non-forbidden woman. (c) If a woman w is free at the end of the algorithm, then it must be that no man ever proposed to w. (d) At the end of the algorithm, there can be a man m and a woman w, such that (m,w) ¢ F, but neither of which is part of any pair in the matching S. (e) At the end of the algorithm, there can be a pair (m, w) e S and a man m' that is free, (m', w) ¢ F, but such that w prefers m' to m.

1. Consider the generalization of stable matching problem where a certain man-woman pairs are forbidden. The set of forbidden pairs is denoted as F. Each man m ranks all the woman w for which (m, w) ¢ F and each woman w ranks all the man m for which (m, w) ¢ F. Consider the following algorithm for finding a stable matching that consists of only unforbidden pairs: Initially all m E M and w e W are free; S = Ø While there is a man m who is free and hasn't proposed to every woman w for which (m,w) ¢ F Choose such a man m Let w be the highest-ranked woman in m's preference list to which m has not yet proposed If w is free: Add (m, w) to solution S Else (w is current matched with m'): If w prefers m' to m m remains free Else Replace (m', w) by (m, w) in S Return solution S Answer true or false for the following questions: (a) Any woman w remains engaged from the point at which she receives her first proposal, and the se- quence of partners to which she is engaged get better and better. (b) If a man m is free at the end of the algorithm, then he must have proposed to every non-forbidden woman. (c) If a woman w is free at the end of the algorithm, then it must be that no man ever proposed to w. (d) At the end of the algorithm, there can be a man m and a woman w, such that (m,w) ¢ F, but neither of which is part of any pair in the matching S. (e) At the end of the algorithm, there can be a pair (m, w) e S and a man m' that is free, (m', w) ¢ F, but such that w prefers m' to m.

Database System Concepts
Database System Concepts
7th Edition
ISBN:9780078022159
Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Chapter1: Introduction
Section: Chapter Questions
Problem 1PE
See similar textbooks
icon
Related questions
Question
1. Consider the generalization of the stable matching problem where certain man-woman pairs are forbidden. The set of forbidden pairs is denoted as \( F \). Each man \( m \) ranks all the women \( w \) for which \((m,w) \notin F\), and each woman \( w \) ranks all the men \( m \) for which \((m,w) \notin F\). Consider the following algorithm for finding a stable matching that consists of only unforbidden pairs: --- Initially all \( m \in M \) and \( w \in W \) are free; \( S = \emptyset \). While there is a man \( m \) who is free and hasn’t proposed to every woman \( w \) for which \((m,w) \notin F\): - Choose such a man \( m \). - Let \( w \) be the highest-ranked woman in \( m \)'s preference list to whom \( m \) has not yet proposed. - If \( w \) is free: - Add \((m,w)\) to solution \( S \). - Else (\( w \) is currently matched with \( m' \)): - If \( w \) prefers \( m' \) to \( m \), \( m \) remains free. - Else, replace \((m',w)\) by \((m,w)\) in \( S \). Return solution \( S \). --- Answer true or false for the following questions: (a) Any woman \( w \) remains engaged from the point at which she receives her first proposal, and the sequence of partners to which she is engaged gets better and better. (b) If a man \( m \) is free at the end of the algorithm, then he must have proposed to every non-forbidden woman. (c) If a woman \( w \) is free at the end of the algorithm, then it must be that no man ever proposed to \( w \). (d) At the end of the algorithm, there can be a man \( m \) and a woman \( w \), such that \((m,w) \notin F\), but neither of which is part of any pair in the matching \( S \). (e) At the end of the algorithm, there can be a pair \((m,w) \in S\) and a man \( m' \) that is
Transcribed Image Text:1. Consider the generalization of the stable matching problem where certain man-woman pairs are forbidden. The set of forbidden pairs is denoted as \( F \). Each man \( m \) ranks all the women \( w \) for which \((m,w) \notin F\), and each woman \( w \) ranks all the men \( m \) for which \((m,w) \notin F\). Consider the following algorithm for finding a stable matching that consists of only unforbidden pairs: --- Initially all \( m \in M \) and \( w \in W \) are free; \( S = \emptyset \). While there is a man \( m \) who is free and hasn’t proposed to every woman \( w \) for which \((m,w) \notin F\): - Choose such a man \( m \). - Let \( w \) be the highest-ranked woman in \( m \)'s preference list to whom \( m \) has not yet proposed. - If \( w \) is free: - Add \((m,w)\) to solution \( S \). - Else (\( w \) is currently matched with \( m' \)): - If \( w \) prefers \( m' \) to \( m \), \( m \) remains free. - Else, replace \((m',w)\) by \((m,w)\) in \( S \). Return solution \( S \). --- Answer true or false for the following questions: (a) Any woman \( w \) remains engaged from the point at which she receives her first proposal, and the sequence of partners to which she is engaged gets better and better. (b) If a man \( m \) is free at the end of the algorithm, then he must have proposed to every non-forbidden woman. (c) If a woman \( w \) is free at the end of the algorithm, then it must be that no man ever proposed to \( w \). (d) At the end of the algorithm, there can be a man \( m \) and a woman \( w \), such that \((m,w) \notin F\), but neither of which is part of any pair in the matching \( S \). (e) At the end of the algorithm, there can be a pair \((m,w) \in S\) and a man \( m' \) that is
Expert Solution
trending now

Trending now

This is a popular solution!

steps

Step by step

Solved in 3 steps

SEE SOLUTIONCheck out a sample Q&A here
Blurred answer
Knowledge Booster
Temporal Difference Learning
Learn more about
Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.
Similar questions
Recommended textbooks for you
Database System Concepts
Database System Concepts
Computer Science
ISBN:
9780078022159
Author:
Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:
McGraw-Hill Education
Starting Out with Python (4th Edition)
Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
Digital Fundamentals (11th Edition)
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
C How to Program (8th Edition)
C How to Program (8th Edition)
Computer Science
ISBN:
9780133976892
Author:
Paul J. Deitel, Harvey Deitel
Publisher:
PEARSON
Database Systems: Design, Implementation, & Manag…
Database Systems: Design, Implementation, & Manag…
Computer Science
ISBN:
9781337627900
Author:
Carlos Coronel, Steven Morris
Publisher:
Cengage Learning
Programmable Logic Controllers
Programmable Logic Controllers
Computer Science
ISBN:
9780073373843
Author:
Frank D. Petruzella
Publisher:
McGraw-Hill Education
SEE MORE TEXTBOOKS