TY - JOUR
T1 - Geometric stable roommates
AU - Arkin, Esther M.
AU - Bae, Sang Won
AU - Efrat, Alon
AU - Okamoto, Kazuya
AU - Mitchell, Joseph S.B.
AU - Polishchuk, Valentin
N1 - Funding Information:
We thank the anonymous reviewer for comments and suggestions, and Piyush Kumar for initiating the discussions on the problem. E. Arkin and J. Mitchell acknowledge support from the National Science Foundation (CCF-0431030, CCF-0528209, CCF-0729019), NASA Ames, and Metron Aviation. V. Polishchuk is supported in part by Academy of Finland grant 118653 (ALGODAN). S.W. Bae is supported in part by the Brain Korea 21 Project.
PY - 2009/1/31
Y1 - 2009/1/31
N2 - We consider instances of the Stable Roommates problem that arise from geometric representation of participants' preferences: a participant is a point in a metric space, and his preference list is given by the sorted list of distances to the other participants. We show that contrary to the general case, the problem admits a polynomial-time solution even in the case when ties are present in the preference lists. We define the notion of an α-stable matching: the participants are willing to switch partners only for a (multiplicative) improvement of at least α. We prove that, in general, finding α-stable matchings is not easier than finding matchings that are stable in the usual sense. We show that, unlike in the general case, in a three-dimensional geometric stable roommates problem, a 2-stable matching can be found in polynomial time.
AB - We consider instances of the Stable Roommates problem that arise from geometric representation of participants' preferences: a participant is a point in a metric space, and his preference list is given by the sorted list of distances to the other participants. We show that contrary to the general case, the problem admits a polynomial-time solution even in the case when ties are present in the preference lists. We define the notion of an α-stable matching: the participants are willing to switch partners only for a (multiplicative) improvement of at least α. We prove that, in general, finding α-stable matchings is not easier than finding matchings that are stable in the usual sense. We show that, unlike in the general case, in a three-dimensional geometric stable roommates problem, a 2-stable matching can be found in polynomial time.
KW - Algorithms
KW - Computational geometry
KW - Consistent preferences
KW - Graph algorithms
KW - Stable roommates with ties
KW - α-Stable matching
UR - http://www.scopus.com/inward/record.url?scp=57749097529&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=57749097529&partnerID=8YFLogxK
U2 - 10.1016/j.ipl.2008.10.003
DO - 10.1016/j.ipl.2008.10.003
M3 - Article
AN - SCOPUS:57749097529
SN - 0020-0190
VL - 109
SP - 219
EP - 224
JO - Information Processing Letters
JF - Information Processing Letters
IS - 4
ER -