Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2503.16052 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909628777889792 |
|---|---|
| author | Kamiyama, Naoyuki |
| author_facet | Kamiyama, Naoyuki |
| contents | The stable roommates problem is a non-bipartite version of the well-known stable matching problem. Teo and Sethuraman proved that, for each instance of the stable roommates problem in a complete graph, there exists a linear inequality system such that there exists a feasible solution to this system if and only if there exists a stable matching in the given instance. The aim of this paper is to extend the result of Teo and Sethuraman to the stable roommates problem with ties. More concretely, we prove that, for each instance of the stable roommates problem with ties in a complete graph, there exists a linear inequality system such that there exists a feasible solution to this system if and only if there exists a super-stable matching in the given instance. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_16052 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Linear Programming Approach to the Super-Stable Roommates Problem Kamiyama, Naoyuki Computer Science and Game Theory Combinatorics The stable roommates problem is a non-bipartite version of the well-known stable matching problem. Teo and Sethuraman proved that, for each instance of the stable roommates problem in a complete graph, there exists a linear inequality system such that there exists a feasible solution to this system if and only if there exists a stable matching in the given instance. The aim of this paper is to extend the result of Teo and Sethuraman to the stable roommates problem with ties. More concretely, we prove that, for each instance of the stable roommates problem with ties in a complete graph, there exists a linear inequality system such that there exists a feasible solution to this system if and only if there exists a super-stable matching in the given instance. |
| title | A Linear Programming Approach to the Super-Stable Roommates Problem |
| topic | Computer Science and Game Theory Combinatorics |
| url | https://arxiv.org/abs/2503.16052 |