✦ LIBER ✦

The Stable Roommates Problem with Ties

✍ Scribed by Robert W. Irving; David F. Manlove

Publisher: Elsevier Science
Year: 2002
Tongue: English
Weight: 183 KB
Volume: 43
Category: Article
ISSN: 0196-6774
DOI: 10.1006/jagm.2002.1219

No coin nor oath required. For personal study only.

✦ Synopsis

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 stability. We present a linear-time algorithm for finding a super-stable matching if one exists, given a stable roommates instance with ties. This contrasts with the known NP-hardness of the analogous problem under weak stability. We also extend our algorithm to cope with preference lists that are incomplete and/or partially ordered. On the other hand, for a given stable roommates instance with ties and incomplete lists, we show that the weakly stable matchings may be of different sizes and the problem of finding a maximum cardinality weakly stable matching is NP-hard, though approximable within a factor of 2.  2002 Elsevier Science (USA)

📜 SIMILAR VOLUMES

An efficient algorithm for the “stable r

An efficient algorithm for the “stable roommates” problem

✍ Robert W Irving 📂 Article 📅 1985 🏛 Elsevier Science 🌐 English ⚖ 938 KB

The Roommate Problem (Mile High Happines

The Roommate Problem (Mile High Happiness)

✍ Mariah Ankenman 📂 Fiction 📅 2020 🏛 Entangled Publishing, LLC (Lovestruck) 🌐 en-AU ⚖ 208 KB 👁 2 views

To Moira “Mo” Rossi, the world is full of sunshine, goodness, and happily ever afters—so of course she figures finding the perfect roomie will be easy. But after four creepos who ask if benefits come with the room and one woman who claims she’s a vampire, Mo is officially desperate. So what if the g

A Polynomial-time Algorithm for the Bist

A Polynomial-time Algorithm for the Bistable Roommates Problem

✍ Jay Sethuraman; Chung-Piaw Teo 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 127 KB

In a recent paper, Weems introduced the bistable matching problem, and asked if a polynomial-time algorithm exists to decide the feasibility of the bistable roommates problem. We resolve this question in the affirmative using linear programming. In addition, we show that several (old and new) result

Bistable Versions of the Marriages and R

Bistable Versions of the Marriages and Roommates Problems

✍ B.P. Weems 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 291 KB

A stable matching for an instance of the stable marriages problem or the stable roommates problem is bistable if it is also a stable matching when the ordering of the input preference lists is reversed. For the stable marriages problem, it is shown that the bistable matchings are a sublattice of the

On the stable exact model matching probl

On the stable exact model matching problem

✍ A.I.G. Vardulakis; N. Karcanias 📂 Article 📅 1985 🏛 Elsevier Science 🌐 English ⚖ 428 KB

On the distributed stable full informati

On the distributed stable full information H∞ minimax problem

✍ Olof J. Staffans 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 351 KB

We study the distributed parameter suboptimal full information H problem for a stable well-posed linear system with control u, disturbance w, state x, and output y. Here u, w, and y are ¸-signals on (0, R) with values in the Hilbert spaces º, ¼, and ½, and the state x is a continuous function of tim