𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Approximability results for stable marriage problems with ties

✍ Scribed by Magnús M. Halldórsson; Robert W. Irving; Kazuo Iwama; David F. Manlove; Shuichi Miyazaki; Yasufumi Morita; Sandy Scott

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

No coin nor oath required. For personal study only.

✦ Synopsis

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. We also consider stable marriage instances in which persons may express unacceptable partners in addition to ties. In this setting, we prove that there are constants ; such that each of the problems of approximating a maximum and minimum cardinality stable matching within factors of ; (respectively) is NP-hard, under strong restrictions. We also give an approximation algorithm for both problems that has a performance guarantee expressible in terms of the number of lists with ties. This signiÿcantly improves on the best-known previous performance guarantee, for the case that the ties are sparse. Our results have applications to large-scale centralized matching schemes.

📜 SIMILAR VOLUMES

The stable marriage problem with restric
The stable marriage problem with restricted pairs
✍ Vânia M.F. Dias; Guilherme D. da Fonseca; Celina M.H. de Figueiredo; Jayme L. Sz 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 210 KB

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

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

Differential approximation results for t
Differential approximation results for the Steiner tree problem
✍ M Demange; J Monnot; V.Th Paschos 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 654 KB

we study the approximability of three versions of the Steiner tree problem. For the first one where the input graph is only supposed connected, we show that it is not approximable within better than IV \ Nj-' for any E E (0, l), where V and N are the vertex-set of the input graph and the set of term

Approximation Results for the Optimum Co
Approximation Results for the Optimum Cost Chromatic Partition Problem
✍ Klaus Jansen 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 246 KB

In this paper, we study the optimum cost chromatic partition OCCP problem for several graph classes. The OCCP problem is the problem of coloring the vertices of a graph such that adjacent vertices get different colors and that the total coloring cost is minimum. We prove several approximation result