𝔖 Bobbio Scriptorium
✦   LIBER   ✦

The stable marriage problem with restricted pairs

✍ Scribed by Vânia M.F. Dias; Guilherme D. da Fonseca; Celina M.H. de Figueiredo; Jayme L. Szwarcfiter

Publisher
Elsevier Science
Year
2003
Tongue
English
Weight
210 KB
Volume
306
Category
Article
ISSN
0304-3975

No coin nor oath required. For personal study only.

✦ Synopsis

A stable matching is a complete matching of men and women such that no man and woman who are not partners both prefer each other to their actual partners under the matching. In an instance of the STABLE MARRIAGE problem, each of the n men and n women ranks the members of the opposite sex in order of preference. It is well known that at least one stable matching exists for every STABLE MARRIAGE problem instance. We consider extensions of the STABLE MARRIAGE problem obtained by forcing and by forbidding sets of pairs. We present a characterization for the existence of a solution for the STABLE MARRIAGE WITH FORCED AND FORBIDDEN PAIRS problem. In addition, we describe a reduction of the STABLE MARRIAGE WITH FORCED AND FORBIDDEN PAIRS problem to the STABLE MARRIAGE WITH FORBIDDEN PAIRS problem. Finally, we also present algorithms for ÿnding a stable matching, all stable pairs and all stable matchings for this extension. The complexities of the proposed algorithms are the same as the best known algorithms for the unrestricted version of the problem.

📜 SIMILAR VOLUMES

Approximability results for stable marri
Approximability results for stable marriage problems with ties
✍ Magnús M. Halldórsson; Robert W. Irving; Kazuo Iwama; David F. Manlove; Shuichi 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 293 KB

We consider instances of the classical stable marriage problem in which persons may include ties in their preference lists. We show that, in such a setting, strong lower bounds hold for the approximability of each of the problems of ÿnding an egalitarian, minimum regret and sex-equal stable matching

The Stable Roommates Problem with Ties
The Stable Roommates Problem with Ties
✍ Robert W. Irving; David F. Manlove 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 183 KB

We study the variant of the well-known stable roommates problem in which participants are permitted to express ties in their preference lists. In this setting, more than one definition of stability is possible. Here we consider two of these stability criteria, so-called super-stability and weak stab