Geometric stable roommates

Esther M. Arkin, Sang Won Bae, Alon Efrat, Kazuya Okamoto, Joseph S.B. Mitchell, Valentin Polishchuk

Research output: Contribution to journalArticlepeer-review

28 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)219-224
Number of pages6
JournalInformation Processing Letters
Issue number4
StatePublished - Jan 31 2009


  • Algorithms
  • Computational geometry
  • Consistent preferences
  • Graph algorithms
  • Stable roommates with ties
  • α-Stable matching

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Signal Processing
  • Information Systems
  • Computer Science Applications


Dive into the research topics of 'Geometric stable roommates'. Together they form a unique fingerprint.

Cite this