direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Stable Roommate with Narcissistic, Single-Peaked, and Single-Crossing Preference

Robert Bredereck (TU Berlin)


The classical Stable Roommate problem asks whether it is possible to have a matching of an even number of agents such that no two agents which are not matched to each other would prefer to be with each other rather than with their assigned partners. We investigate Stable Roommate with complete (i.e. every agent can be matched with every other agent) or incomplete preferences, with ties (i.e. two agents are considered of equal value to some agent) or without ties. It is known that in general allowing ties makes the problem NP-complete. We provide algorithms for Stable Roommate that are, compared to those in the literature, more efficient when the input pref-erences are complete and have some structural property, such as being narcissistic, single-peaked, and single-crossing. However, when the preferences are incomplete and have ties, we show that being single-peaked and single-crossing does not reduce the computational complexity---Stable Roommate remains NP-complete.

This is a joint work with Jiehua Chen, Ugo Paavo Finnendahl, and Rolf Niedermeier that was presented at ADT 2017 in Luxemburg. In this talk I will also highlight some delevopments from preparing the journal version.


Robert Bredereck
TEL 512

Back to the research colloquium site.

To top

Zusatzinformationen / Extras