Given a possibly unstable matching in the stable marriage problem, let it be possible to query an oracle about any pair of people, asking whether that pair would rather be with each other than with their assigned partners. Create an algorithm to minimize the number of queries needed to discover such a pair if one exists, or to conclude correctly that the matching is stable.
Given such an algorithm, create matchings which cause the algorithm to exhibit worst-case behavior.
No comments :
Post a Comment