𝔖 Bobbio Scriptorium
✦   LIBER   ✦

An efficient algorithm for the “stable roommates” problem

✍ Scribed by Robert W Irving

Publisher
Elsevier Science
Year
1985
Tongue
English
Weight
938 KB
Volume
6
Category
Article
ISSN
0196-6774

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

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

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

An Efficient Algorithm for the Complex R
An Efficient Algorithm for the Complex Roots Problem
✍ C.Andrew Neff; John H. Reif 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 406 KB

Given a univariate polynomial f (z) of degree n with complex coefficients, whose norms are less than 2 m in magnitude, the root problem is to find all the roots of f (z) up to specified precision 2 ϪȐ . Assuming the arithmetic model for computation, we provide an algorithm which has complexity O(n l