Please use this identifier to cite or link to this item:
https://scholarbank.nus.edu.sg/handle/10635/249424
| Title: | CHARACTERIZE WEAK AND SUPER STABILITY OF THE ROOMMATE PROBLEM UNDER WEAK PREFERENCES | Authors: | YU BIN | ORCID iD: |  orcid.org/0009-0003-8395-3623 |
Keywords: | stable roommate matching, stable partition, computation complexity | Issue Date: | 20-Mar-2024 | Citation: | YU BIN (2024-03-20). CHARACTERIZE WEAK AND SUPER STABILITY OF THE ROOMMATE PROBLEM UNDER WEAK PREFERENCES. ScholarBank@NUS Repository. | Abstract: | This paper presents a new structure called the "weak-stable partition" and "super-stable partition" which characterizes the weak and super stability of the roommate problem under weak preferences and extends the no-odd ring condition of stable roommate matching established in \cite{chung2000existence}. We demonstrate that finding such a stable partition under weak stability conditions is an NP-complete problem. Finding a stable partition under super stability condition admits polynomial algorithm. | URI: | https://scholarbank.nus.edu.sg/handle/10635/249424 |
| Appears in Collections: | Master's Theses (Open) |
Show full item record
Files in This Item:
| File | Description | Size | Format | Access Settings | Version | |
|---|---|---|---|---|---|---|
| YB.pdf | 443.21 kB | Adobe PDF | OPEN | None | View/Download |
Google ScholarTM
Check
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.