Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2510.16385 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917024384417792 |
|---|---|
| author | Kamiyama, Naoyuki |
| author_facet | Kamiyama, Naoyuki |
| contents | The stable roommates problem is a non-bipartite version of the stable matching problem in a bipartite graph. In this paper, we consider the stable roommates problem with ties. In particular, we focus on strong stability, which is one of the main stability concepts in the stable roommates problem with ties. We propose a new polynomial-time algorithm for the problem of checking the existence of a strongly stable matching in the stable roommates problem with ties. More concretely, we extend the linear programming approach of Abeledo and Blum to the stable roommates problem with strict preferences to our problem. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_16385 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | The Strongly Stable Roommates Problem and Linear Programming Kamiyama, Naoyuki Computer Science and Game Theory The stable roommates problem is a non-bipartite version of the stable matching problem in a bipartite graph. In this paper, we consider the stable roommates problem with ties. In particular, we focus on strong stability, which is one of the main stability concepts in the stable roommates problem with ties. We propose a new polynomial-time algorithm for the problem of checking the existence of a strongly stable matching in the stable roommates problem with ties. More concretely, we extend the linear programming approach of Abeledo and Blum to the stable roommates problem with strict preferences to our problem. |
| title | The Strongly Stable Roommates Problem and Linear Programming |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2510.16385 |