Jiehua Chen

Paper appeared at ESA 2022 (Track A): Multi-Dimensional Stable Roommates in 2-Dimensional Euclidean Space

Posted on Sep 05, 2022 by Jiehua Chen

Summary

We investigate the Euclidean 𝖽-Dimensional Stable Roommates problem, which asks whether a given set $V$ of $𝖽\cdot n$ points from the 2-dimensional Euclidean space can be partitioned into n disjoint (unordered) subsets $\Pi = $V_1, \ldots, V_n$ with$	V_i	= 𝖽 $for each$ V_i \in \Pi $such that$ \Pi$$ is {stable}.
Here, stability means that no point subset $W \subseteq V$ is blocking $\Pi$ , and $W$ is said to be blocking $\Pi$ if $$	W	= 𝖽 $such that$ \Sigma_{w’ \in W} \delta(w,w’) < \Sigma_{v \in \Pi(w)}\delta(w,v) $holds for each point$ w \in W $, where$ \Pi(w) $denotes the subset$ V_i \in \Pi $which contains$ w $and$ \delta(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$ 𝖽 \ge 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].

====================================

The conference version and the long version of the paper can be found at ESA22 and on arXiv.