A Linear Programming Approach to the Super-Stable Roommates Problem
By: Naoyuki Kamiyama
Potential Business Impact:
Finds fair roommate pairings, even with tricky choices.
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.
Similar Papers
The Strongly Stable Roommates Problem and Linear Programming
CS and Game Theory
Finds fair room assignments when people have preferences.
Perspectives on Unsolvability in the Roommates Problem
CS and Game Theory
Finds ways to pair people when no perfect match exists.
Unsolvability and Beyond in Many-To-Many Non-Bipartite Stable Matching
Data Structures and Algorithms
Finds best matches for groups with different needs.