<div class="csl-bib-body">
<div class="csl-entry">Chen, J., & Roy, S. (2022). Multi-Dimensional Stable Roommates in 2-Dimensional Euclidean Space. In S. Chechik, G. Navarro, E. Rotenberg, & G. Herman (Eds.), <i>30th Annual European Symposium on Algorithms (ESA 2022)</i> (pp. 1–16). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ESA.2022.36</div>
</div>
-
dc.identifier.uri
http://hdl.handle.net/20.500.12708/150294
-
dc.description.abstract
We investigate the Euclidean d-Dimensional Stable Roommates problem, which asks whether a given set V of d n points from the 2-dimensional Euclidean space can be partitioned into n disjoint (unordered) subsets Π = {V1, , Vn} with |Vi| = d for each Vi ϵ Π such that Π is stable. Here, stability means that no point subset W ⊆ V is blocking Π, and W is said to be blocking Πif |W| = d such that Σ w ϵW δ(w,w) < Σ vϵΠ(w) δ(w, v) holds for each point w ϵ W, where Π (w) denotes the subset Vi ϵ Π which contains w and δ(a, b) denotes the Euclidean distance between points a and b. Complementing the existing known polynomial-time result for d = 2, we show that such polynomial-time algorithms cannot exist for any fixed number d ≥ 3 unless P=NP. Our result for d = 3 answers a decade-long open question in the theory of Stable Matching and Hedonic Games [18, 1, 10, 26, 21].
en
dc.language.iso
en
-
dc.relation.ispartofseries
Leibniz International Proceedings in Informatics (LIPIcs)
-
dc.relation.isversionof
https://doi.org/10.48550/arXiv.2108.03868
-
dc.rights.uri
http://creativecommons.org/licenses/by/4.0/
-
dc.subject
coalition formation games
en
dc.subject
Euclidean preferences
en
dc.subject
multidimensional stable roommates
en
dc.subject
NP-hardness
en
dc.subject
stable cores
en
dc.subject
stable matchings
en
dc.title
Multi-Dimensional Stable Roommates in 2-Dimensional Euclidean Space