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

VL - 109

SP - 219

EP - 224

JO - Information Processing Letters

JF - Information Processing Letters

SN - 0020-0190

IS - 4

ER -