2026-07-24T00:34:42Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16974 2024-03-06T10:58:51Z ddc:004 open_access

Multi-Dimensional Stable Roommates in 2-Dimensional Euclidean Space Chen, Jiehua Roy, Sanjukta stable matchings multidimensional stable roommates Euclidean preferences coalition formation games stable cores NP-hardness We investigate the Euclidean 𝖽-Dimensional Stable Roommates problem, which asks whether a given set V of 𝖽⋅ n points from the 2-dimensional Euclidean space can be partitioned into n disjoint (unordered) subsets Π = {V₁,…,V_{n}} with |V_i| = 𝖽 for each V_i ∈ Π such that Π is {stable}. Here, {stability} means that no point subset W ⊆ V is blocking Π, and W is said to be {blocking} Π if |W| = 𝖽 such that ∑_{w' ∈ W}δ(w,w') < ∑_{v ∈ Π(w)}δ(w,v) holds for each point w ∈ W, where Π(w) denotes the subset V_i ∈ Π which contains w and δ(a,b) denotes the Euclidean distance between points a and b. Complementing the existing known polynomial-time result for 𝖽 = 2, we show that such polynomial-time algorithms cannot exist for any fixed number 𝖽 ≥ 3 unless P=NP. Our result for 𝖽 = 3 answers a decade-long open question in the theory of Stable Matching and Hedonic Games [Iwama et al., 2007; Arkin et al., 2009; Vladimir G. Deineko and Gerhard J. Woeginger, 2013; Vladimir G. Deineko and Gerhard J. Woeginger, 2013; David F. Manlove, 2013]. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jiehua Chen and Sanjukta Roy 2022 Is Part Of LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2022.36 urn:nbn:de:0030-drops-169741 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.36 eng https://creativecommons.org/licenses/by/4.0/legalcode